「Codeforces 338D」GCD Table

发表于 | | 阅读次数:
字数统计: 695 字

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%