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.

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).

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

100 100 55 2 1 2 1output
YESinput
100 8 55 2 1 2 1output
NOinput
100 100 71 2 3 4 5 6 7output
NONote
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.
題目大意：給出一個n*m的數表，(i,j)=GCD(i,j).然后給出一個序列a1...ak問序列是否在數表中出現過。
題解：擴展中國剩余定理
首先可以確定行一定是a1...ak的最小公倍數的倍數，如果lcm>n，那么無解。
然后設第一列為x 
x=a1*b1  (其中b表示a1的整數倍，因為a1為x的gcd，所以一定能表示成a1*b1的形式)
x+1=a2*b2
x+2=a3*b3
.....
可以把式子都轉換成線性同余方程的形式x=a[i]-i+1 (mod a[i])
用擴展中國剩余定理合并，然后求出解x
如果解出來的x為0，那么需要先加上r，再進行判斷。
如果x>m-k+1,則無解。
然后再帶入驗證一下答案，就可以輸出最終判斷的結果了。
#include<iostream>  #include<cstring>  #include<algorithm>  #include<cstdio>  #include<cmath>  #define N 10003  #define LL long long   using namespace std;  LL n,m,a[N],c[N],r[N];  int k;  LL mul(LL a,LL b,LL mod){	LL ans=0; 	while (b) {		if (b&1) ans=(ans+a)%mod;		b>>=1;		a=(a+a)%mod;	}	return ans%mod;}LL gcd(LL x,LL y)  {      LL r;      while (y) {          r=x%y;          x=y; y=r;      }      return x;  }  void exgcd(LL a,LL b,LL &x,LL &y){	if (!b) {		x=1; y=0; return;	}	exgcd(b,a%b,x,y);	LL t=y;	y=x-(a/b)*y;	x=t;}LL inv(LL a,LL b){	LL x,y;	exgcd(a,b,x,y);	return (x%b+b)%b;}bool check(LL a1,LL a2,LL r1,LL r2,LL &aa,LL &rr)  {       LL c=a2-a1; LL d=gcd(r1,r2);    // cout<<r1<<" "<<r2<<" "<<d<<endl;	 if (c%d) return 0;	 c/=d; r1/=d; r2/=d;	 LL x=inv(r1,r2); c=(c%r2+r2)%r2;	 rr=r1*r2*d;	 x=mul(x,c,r2);	 x=mul(mul(x,r1,rr),d,rr)+a1;	 aa=(x%rr+rr)%rr;	 return 1; }  int main()  {     freopen("a.in","r",stdin);     scanf("%I64d%I64d%d",&n,&m,&k);      for (int i=1;i<=k;i++) scanf("%I64d",&c[i]);      LL lcm=c[1]/gcd(c[1],c[2])*c[2];      for (int i=3;i<=k;i++){       lcm=lcm/gcd(lcm,c[i])*c[i];       if (lcm>n) {          printf("NO/n");          return 0;       }      }      for (int i=1;i<=k;i++) r[i]=c[i],a[i]=c[i]-i+1;	LL a1,a2,r1,r2,rr,aa;	a1=aa=a[1]; r1=rr=r[1];	for (int i=2;i<=k;i++) {		a2=a[i]; r2=r[i];		if (a2<0) a2=(a2%r2+r2)%r2;		if(!check(a1,a2,r1,r2,aa,rr)) {			printf("NO/n");			return 0;		}	    a1=aa; r1=rr;	    //cout<<aa<<" "<<rr<<endl;	}	//cout<<aa<<endl;	if (!aa) aa+=rr;	if (aa>m-k+1) {		printf("NO/n");		return 0;	}	for (int i=1;i<=k;i++) {		LL t=gcd(lcm,aa+i-1);		if (t!=c[i]) {			printf("NO/n");			return 0;		}	}	printf("YES/n");}