$$\Large\texttt{My Blog}$$


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

#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;
}