什么都不会只能学数论QAQ
英文原题不贴了
题意：
有一张N*M的表格，i行j列的元素是gcd(i,j)
读入一个长度为k，元素大小不超过10^12的序列a[1..k]，问这个序列是否在表格的某一行中出现过
1<=N,M<=10^12
1<=k<=10^4
恩
首先显然x=lcm(a[i])
然后(y+i-1)%a[i]==0
即y%[i]=1-n
然后就神奇地变成了中国剩余定理
求出x和y后判无解即可，情况比较多
首先如果x和y超过n,m的范围或<0显然不对
然后注意枚举i看gcd(x,y+i-1)是否等于a[i]
恩？好像也不多
注意因为这个表示直接定义好的并没有实质地给出来，所以n,m都可以把int爆了
所有的计算过程都需要longlong？
什么都不会只能学数论QAQ
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
ll rd(){ll z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
ll n,m,o; ll mo[],a[];
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){ x=,y=; return a;}
ll d=exgcd(b,a%b,x,y);
ll tmp=x; x=y,y=tmp-a/b*y;
return d;
}
ll chn(){
ll M=mo[],A=a[],k,y;
for(int i=;i<=o;++i){
ll tmp=a[i]-A,d=exgcd(M,mo[i],k,y);
if(tmp%d) return -;
ll tm=mo[i]/d;
k=(k*tmp/d%tm+tm)%tm,A+=k*M,M=M*mo[i]/d,A=(A+M)%M;
}
return A;
}
int main(){freopen("ddd.in","r",stdin);
cin>>n>>m>>o;
for(int i=;i<=o;++i) mo[i]=rd(),a[i]=-i;
int y=chn();
ll x=,d;
for(int i=;i<=o;++i){
d=exgcd(x,mo[i],d,d);
x=x*mo[i]/d;
}
if(!y) y=x;
if(y< || y+o->m || x>n){ cout<<"NO"<<endl; return ;}
for(int i=;i<=o;++i)if(exgcd(x,y+i-,d,d)!=mo[i]){ cout<<"NO"<<endl; return ;}
cout<<"YES"<<endl;
return ;
}