CodeForces 338D GCD Table-白红宇

CodeForces 338D GCD Table

阅读量：6213 次

发布时间：2019-06-21

本文共 3836 字，大约阅读时间需要 12 分钟。

Consider a table G of size n × m such that G(i, j) = GCD(i, j) for all 1 ≤ i ≤ n, 1 ≤ j ≤ m. GCD(a, b) is the greatest common divisor of numbers a and b.

You have a sequence of positive integer numbers a1, a2, ..., ak. We say that this sequence occurs in table G if it coincides with consecutive elements in some row, starting from some position. More formally, such numbers 1 ≤ i ≤ n and 1 ≤ j ≤ m - k + 1 should exist that G(i, j + l - 1) = al for all 1 ≤ l ≤ k.

Determine if the sequence a occurs in table G.

Input

The first line contains three space-separated integers n, m and k (1 ≤ n, m ≤ 1012; 1 ≤ k ≤ 10000). The second line contains k space-separated integers a1, a2, ..., ak (1 ≤ ai ≤ 1012).

Output

Print a single word "YES", if the given sequence occurs in table G, otherwise print "NO".

Examples

input

100 100 5 5 2 1 2 1

output

YES

input

100 8 5 5 2 1 2 1

output

NO

input

100 100 7 1 2 3 4 5 6 7

output

NO

Note

Sample 1. The tenth row of table G starts from sequence {1, 2, 1, 2, 5, 2, 1, 2, 1, 10}. As you can see, elements from fifth to ninth coincide with sequence a.

Sample 2. This time the width of table G equals 8. Sequence a doesn't occur there.

数学问题扩展中国剩余定理

首先可以知道这个数列如果存在，它最早会出现在“所有a[]的lcm”这一行，而如果lcm行都没有，之后的行每个数都成倍扩大，更不可能出现目标数列。

我们假设数列第一个元素在第x列，因为是在gcd表上，所以a[i]一定是x的因数，也就是$ x = a[i]*k $

这个式子的形式看上去很熟悉？ $ x \equiv 0 (\bmod a[i])$

像这样继续把每个式子都列出来：

$x \equiv 0 (\bmod a_{1})$

$x+1 \equiv 0 (\bmod a_{2})$

$x+2 \equiv 0 (\bmod a_{3})$

$x+3 \equiv 0 (\bmod a_{4})$

$x+4 \equiv 0 (\bmod a_{5})$

这样就得到了一串$x \equiv a[i]-i+1 (\bmod a_{i})$ 形式的同余方程。

然后用中国剩余定理解就行……吗？注意到这些b[]可能并不是互质的，我们需要扩展中国剩余定理

扩展中国剩余定理？听起来好帅

实际上就是用扩展欧几里得合并中国剩余定理，消除不互质的模数之间的gcd的影响。

我们知道中国剩余定理就是用扩展欧几里得算法推出来的，那么它实际上就是扩展·扩展·扩展欧几里得算法？

一连串花式化简好麻烦的，用latex写公式更麻烦。

推荐左转http://blog.csdn.net/clove_unique/article/details/54571216

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define LL long long 7 using namespace std; 8 const int mxn=10010; 9 LL read(){10     LL x=0,f=1;char ch=getchar();11     while(ch<'0' || ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}12     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}13     return x*f;14 }15 LL ksmul(LL a,LL b,LL p){16     LL res=0;17     if(b<0)b=-b,a=-a;18     while(b){19         if(b&1)(res+=a)%=p;20         a<<=1;a%=p;21         b>>=1;22     }23     return res;24 }25 LL gcd(LL a,LL b){26     return (!b)?a:gcd(b,a%b);27 }28 LL exgcd(LL a,LL b,LL &x,LL &y){29     30     if(!b){x=1;y=0;return a;}31     LL tmp=exgcd(b,a%b,x,y);32     LL c=x;x=y;y=c-a/b*y;33     return tmp;34 }35 LL inv(LL a,LL b){36     LL x,y;37     exgcd(a,b,x,y);38     x=(x%b+b)%b;39     if(!x)x+=b;40     return x;41 }42 LL n,M,k,lcm;43 LL a[mxn],m[mxn],c[mxn];44 int main(){45     int i,j;46     n=read();M=read();k=read();47     for(i=1;i<=k;i++)a[i]=read();48     lcm=a[1];49     for(i=2;i<=k;i++){50         lcm=lcm/gcd(lcm,a[i])*a[i];51         if(lcm>n){printf("NO\n");return 0;}52     }53     for(i=1;i<=k;i++)m[i]=a[i],c[i]=a[i]-i+1LL;54     LL m1=m[1],c1=c[1];55     for(i=2;i<=k;i++){56         LL m2=m[i],c2=c[i];57         LL tmp=gcd(m1,m2);58         if((c2-c1)%tmp){printf("NO\n");return 0;}//无解59         LL m3=m1/tmp*m2,c3=inv(m1/tmp,m2/tmp);60         c3=ksmul(c3,(c2-c1)/tmp,m2/tmp);61         c3=ksmul(c3,m1,m3);62         c3=((c3+c1)%m3+m3)%m3;63         m1=m3;c1=c3;64     }65     if(!c1)c1+=m1;66     if(c1>M-k+1){printf("NO\n");return 0;}67     for(int i=1;i<=k;i++){68         LL tmp=gcd(lcm,c1+i-1);69         if(tmp!=a[i]){printf("NO\n");return 0;}70     }71     printf("YES\n");72     return 0;73 }

转载于:https://www.cnblogs.com/SilverNebula/p/6814762.html

你可能感兴趣的文章