http://codeforces.com/problemset/problem/338/D
题意：
有一张n*m的表格，其中第i行第j列的数为gcd(i,j)
给出k个数
问在这张表格中是否 有某一行中连续的某一部分 就是 这k个数
题意转化：
是否存在 一对i，j
满足gcd（i，j）=a1，gcd（i，j+1）=a2，…… gcd（i，j+k-1）=ak
直观上感觉：
i要满足的必要条件是 i | lcm（a1，a2……ak）
j要满足的必要条件是
j= a1*k1，j+1=a2*k2……，j+k-1=ak*k_k
相当于
j ≡ 0 mod a1
j ≡ -1 mod a2
……
j≡ -(k-1) mod ak
利用扩展中国剩余定理可以求出 满足条件的最小的j
我们令i=lcm（a1，a2……ak）
去检验 是否满足 gcd（i，j+m-1）= a_m m∈[1,k]
若满足条件输出YES，否则输出NO
为什么用满足必要条件的最小的i和j检验?
证明 i= lcm（a1，a2……ak）是唯一满足要求的i：
若还存在一个 i*x 满足条件，那么
将 i ， i*x，j 质因数分解，存在一个 p^k 能整除i*x、j，不能整除i
∵ i= lcm（a1，a2……ak）
∴i的质因数分解的任意一项 必须能整除 a中的某一个
而 p^k 不能整除a 中的任意一个，否则i的质因数分解包含 p^k
证明 满足 j ≡ -（h-1） mod a[h] 的最小的j一定满足要求
若存在一个j*x 满足条件，而j不满足条件
即 存在一个h，满足 gcd（i，j+h-1）< a[h]，gcd（i，j*x+h-1）= a[h]
将 j，j*x ，a[h]质因数分解，j*x 中 存在一个p^k2，满足
j 中 为 p^k1，a[h] 中为 p^k2 ， 且 k1<k2
∵ j ≡ -（h-1） mod a[h]
即 j= a[h]*s - h+1
∴ j+h-1 = a[h]*s，所以k1>=k2
所以 最小的j一定满足要求
#include<cstdio>
#include<iostream> using namespace std; typedef long long LL; #define N 10001 LL a[N]; LL n1,a1; LL lcm; template<typename T>
void read(T &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} LL gcd(LL a,LL b) { return !b ? a : gcd(b,a%b); } bool judge_lcm(int k,LL n)
{
lcm=;
for(int i=;i<=k;++i)
{
lcm=lcm/gcd(lcm,a[i])*a[i];
if(lcm>n) return false;
}
return true;
} void exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b) { x=; y=; return;}
exgcd(b,a%b,y,x); y-=a/b*x;
} LL mul(LL a,LL b,LL mod)
{
LL res=;
while(b)
{
if(b&) { b--; res+=a; res%=mod; }
a<<=; a%=mod; b>>=;
}
return res;
} LL merge(LL n2,LL a2)
{
LL d=gcd(n1,n2),c=a2-a1;
if(c%d) return -;
LL x,y;
exgcd(n1/d,n2/d,x,y);
LL mod=n2/d;
x=(x%mod+mod)%mod;
LL k=(mul(c/d,x,mod)%mod+mod)%mod;
a1=(a1+n1*k%(mod*n1))%(mod*n1);
n1*=mod;
return a1;
} int main()
{
LL n,m; int k;
read(n); read(m); read(k);
for(int i=;i<=k;++i) read(a[i]);
if(!judge_lcm(k,n))
{
puts("NO");
return ;
}
n1=a[]; a1=;
LL j=a1;
for(int i=;i<=k;++i)
{
j=merge(a[i],a[i]-(i-));
if(j==-) { puts("NO"); return ; }
}
if(!j) j=lcm;
if(j+k->m) { puts("NO"); return ;}
for(int i=;i<=k;++i)
if(gcd(lcm,j+i-)!=a[i]) { puts("NO"); return ; }
puts("YES");
}