「Codeforces 338D」GCD Table

Description

题目链接:Codeforces 338D

有一张 $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$,即满足下列同余方程:

这个方程显然可以通过扩展中国剩余定理来求解 $y$ 即可。

但是我们发现,求出 $y$ 之后的解 $(x,y)$ 不一定就是合法的,这是为什么呢?

其实我们通过这样的思路,推导出解只满足必要性,而不满足充分性。因此我们还需要将 $(x,y)$ 代入 $\gcd(x,y+i-1)=a_i(1\le i\le k)$ 验证。

时间复杂度:$O(k\log a_i)​$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}
0%