题解 CF338D 【GCD Table】
Siyuan
2019-02-08 11:05:32
[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-Codeforces-338D-GCD-Table/)
---
## Description
> 题目链接：[Codeforces 338D](https://codeforces.com/contest/338/problem/D)
有一张 $n\times m$ 的表格，第 $i$ 行第 $j$ 列的元素是 $\gcd(i,j)$。给定一个长度为 $k$ 的序列 $a_i$，询问是否存在 $x,y$，满足 $\forall i,1\le i\le k,\gcd(x,y+i-1)=a_i$（即这个序列在表格的某一行出现过）。
数据范围：$1\le n,m\le 10^{12}$，$1\le k\le 10^4$，$1\le a_i\le 10^{12}$
------
## Solution
由于我们要保证 $\gcd(x,y)=a_i$，显然 $\operatorname{lcm}(a_1,a_2,\dots,a_k)\mid x$。
我们尝试证明：如果有解，那么 $x$ 的值可以为 $\operatorname{lcm}(a_1,a_2,\dots,a_k)$。
如果有解，且 $x=K\cdot\operatorname{lcm}(a_1,a_2,\dots,a_k)$，那么意味着 $\gcd(K,y)=0$，这样一来我们给 $y$ 平白无故地增加了限制。因此如果 $x=K\cdot\operatorname{lcm}(a_1,a_2,\dots,a_k)$ 时有解，那么在 $x=\operatorname{lcm}(a_1,a_2,\dots,a_k)$ 时一定也有解。
在确定了 $x$ 的值之后，还需要满足 $a_i\mid y+i-1$，即满足下列同余方程：
$$\begin{cases}y=0\pmod{a_1} \\y=-1\pmod{a_2} \\\vdots \\y=-k+1\pmod{a_k}\end{cases}$$
这个方程显然可以通过**扩展中国剩余定理**来求解 $y$ 即可。
但是我们发现，求出 $y$ 之后的解 $(x,y)$ 不一定就是合法的，这是为什么呢？
其实我们通过这样的思路，推导出解**只满足必要性**，而**不满足充分性**。因此我们还需要将 $(x,y)$ 代入 $\gcd(x,y+i-1)=a_i(1\le i\le k)$ 验证。
**时间复杂度**：$O(k\log a_i)$
------
## Code
```cpp
#include <cstdio>
typedef long long LL;
const int N=1e4+5;
int k;
LL x,y,m[N],r[N];
LL mul(LL x,LL p,LL mod) {
if(p<0) x=-x,p=-p;
LL ret=0;
for(;p;p>>=1,x=(x+x)%mod) if(p&1) ret=(ret+x)%mod;
return ret;
}
LL exgcd(LL a,LL b,LL &x,LL &y) {
if(!b) {x=1,y=0;return a;}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x; return d;
}
LL gcd(LL x,LL y) {
return y?gcd(y,x%y):x;
}
LL lcm(LL x,LL y) {
return x/gcd(x,y)*y;
}
LL China(int n) {
LL M=m[1],R=r[1];
for(int i=2;i<=n;++i) {
LL a=M,b=m[i],c=r[i]-R,x,y,d=exgcd(a,b,x,y);
if(c%d) return -1;
a/=d,b/=d,c/=d,x=(mul(x,c,b)+b)%b;
R+=x*M,M*=m[i]/d,R=(R+M)%M;
}
R=(R+M-1)%M+1;
if(R<1||R+k-1>y) return -1;
return R;
}
int main() {
scanf("%lld%lld%d",&x,&y,&k);
LL xx=1;
for(int i=1;i<=k;++i) {
scanf("%lld",&m[i]);
if((xx=lcm(xx,m[i]))>x) return puts("NO"),0;
r[i]=((m[i]-i+1)%m[i]+m[i])%m[i];
}
LL yy=China(k);
if(yy==-1) return puts("NO"),0;
for(int i=1;i<=k;++i) {
if(gcd(xx,yy+i-1)!=m[i]) return puts("NO"),0;
}
return puts("YES"),0;
}
```