【CF#338D】GCD Table

【题目描述】

有一张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]即可

 1 /*************
 2   CF#338D
 3   by chty
 4   2016.11.3
 5 *************/
 6 #include<iostream>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<cstring>
10 #include<ctime>
11 #include<cmath>
12 #include<algorithm>
13 using namespace std;
14 typedef long long ll;
15 ll n,m1,K,A,M,ans,lcm(1),m[10010],a[10010];
16 inline ll read()
17 {
18     ll x=0,f=1;  char ch=getchar();
19     while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
20     while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
21     return x*f;
22 }
23 ll gcd(ll a,ll b) {return !b?a:gcd(b,a%b);}
24 void exgcd(ll a,ll b,ll &g,ll &x,ll &y)
25 {
26     if(b==0)  {x=1; y=0; g=a; return;}
27     exgcd(b,a%b,g,x,y);
28     ll t=x;x=y;y=t-a/b*y;
29 }
30 ll China()
31 {
32     for(ll i=1;i<=K;i++)  a[i]=1-i;
33     A=a[1],M=m[1];
34     for(ll i=2;i<=K;i++)
35     {
36         ll k,y,da=a[i]-A,g;
37         exgcd(M,m[i],g,k,y);
38         if(da%g)  return -1;
39         ll t=m[i]/g;
40         k*=da/g;
41         k=(k%t+t)%t;
42         A+=k*M;
43         M=M*m[i]/g;
44         A=(A+M)%M;
45     }
46     return A;
47 }
48 bool check()
49 {
50     if(lcm>n)  return 0;
51     ll ans=China();
52     if(ans<0)  return 0;
53     if(ans==0)  ans=lcm;
54     if(ans+K-1>m1)  return 0;
55     for(ll i=1;i<=K;i++)  if(gcd(lcm,ans+i-1)!=m[i])  return 0;
56     return 1;
57 }
58 int main()
59 {
60     //freopen("cin.in","r",stdin);
61     //freopen("cout.out","w",stdout);
62     n=read();  m1=read();  K=read();
63     for(ll i=1;i<=K;i++)  m[i]=read();
64     for(ll i=1;i<=K;i++)
65     {
66         lcm=lcm/gcd(lcm,m[i])*m[i];
67         if(lcm>n) break;
68     }
69     check()?puts("YES"):puts("NO");
70     return 0;
71 }