【题目描述】

有一张N,M<=10^12的表格,i行j列的元素是gcd(i,j)

读入一个长度不超过10^4,元素不超过10^12的序列a[1..k],问是否在某一行中出现过

【题解】

要保证gcd(x,y)=a[i],显然x=lcm(a[1],a[2]……a[k])

然后y%a[1]=0,即(y+i-1)%a[i]=0

即y%a[1]=0

y%a[2]=-1

……

y%a[n]=-(n-1)

这就转化为了中国剩余定理

求出y之后,只需验证gcd(x,y+i-1)=a[i]即可

 /*************
CF#338D
by chty
2016.11.3
*************/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,m1,K,A,M,ans,lcm(),m[],a[];
inline ll read()
{
ll x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}
void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
{
if(b==) {x=; y=; g=a; return;}
exgcd(b,a%b,g,x,y);
ll t=x;x=y;y=t-a/b*y;
}
ll China()
{
for(ll i=;i<=K;i++) a[i]=-i;
A=a[],M=m[];
for(ll i=;i<=K;i++)
{
ll k,y,da=a[i]-A,g;
exgcd(M,m[i],g,k,y);
if(da%g) return -;
ll t=m[i]/g;
k*=da/g;
k=(k%t+t)%t;
A+=k*M;
M=M*m[i]/g;
A=(A+M)%M;
}
return A;
}
bool check()
{
if(lcm>n) return ;
ll ans=China();
if(ans<) return ;
if(ans==) ans=lcm;
if(ans+K->m1) return ;
for(ll i=;i<=K;i++) if(gcd(lcm,ans+i-)!=m[i]) return ;
return ;
}
int main()
{
//freopen("cin.in","r",stdin);
//freopen("cout.out","w",stdout);
n=read(); m1=read(); K=read();
for(ll i=;i<=K;i++) m[i]=read();
for(ll i=;i<=K;i++)
{
lcm=lcm/gcd(lcm,m[i])*m[i];
if(lcm>n) break;
}
check()?puts("YES"):puts("NO");
return ;
}

最新文章

  1. 参数*args和**args区别
  2. jQuery 学习笔记(函数调用机制)
  3. HTTP中缓存相关
  4. Angularjs简介
  5. jQuery入门第三
  6. 6.基于ZMQ的游戏网络层基础架构
  7. 锁定表头和固定列(Fixed table head and columns)
  8. Django启动报错笔记
  9. mac+php+nginx+laravel配置启动
  10. linux代码笔记
  11. python 绘图 异常点绘制使用 ax.plot(abnormal_points[&#39;ds&#39;], abnormal_points[&#39;y&#39;], &quot;rX&quot;, label=&#39;abnormal points&#39;)
  12. 20.Scrapy日常练手
  13. IR Cut Filter
  14. Incorrect column count: expected 1, actual 5
  15. memcached 的配置及 spymemcached 客户端简单使用
  16. 【bzoj2085】[Poi2010]Hamsters Hash+倍增Floyd
  17. PostgreSQL 的日期函数用法举例
  18. HttpServlet容器响应Web客户流程
  19. 【BZOJ3697】采药人的路径(点分治)
  20. Javascript: 动态显示进度条

热门文章

  1. OpenCV-Python cv2.imdecode()和cv2.imencode() 图片解码和编码
  2. 【工作】to-do-list
  3. python库之threading
  4. hibernate正向工程生成数据库
  5. 【转】C# Socket编程(3)编码和解码
  6. 洛谷P3111 [USACO14DEC]牛慢跑Cow Jog_Sliver
  7. python中的单元测试pyUnit
  8. jQuery ajax submit form 被拦截问题的解决
  9. strtotime出现时区问题不一致的解决方法
  10. week01—绪论