「CF338D」GCD Table

problem

题意

有一张$n\times m$的表，其中第$i$行第$j$列的元素是$gcd(i,j)$。

给定一个长度为$k$的序列$a$，询问在表中是否存在一对$(x,y)$使得$\forall i\in[1,k],a_i=gcd(x,y+i-1)$

Solutions

以下引自@siyuan的题解

---

Solution

由于我们要保证 $gcd(x,y)=a_i$，显然 $lcm(a_1,a_2,…,a_k)∣x$。

我们尝试证明：如果有解，那么$x$的值可以为$lcm(a_1,a_2,…,a_k)$。

如果有解，且$x=K\times lcm(a1,a2,…,ak)$，那么意味着$gcd(K,y)=0$，这样一来我们给$y$平白无故地增加了限制。因此如果 $x=K\times lcm(a_1,a_2,…,a_k)$时有解，那么在 $x=lcm(a_1,a_2,…,a_k)$时一定也有解。

在确定了$x$的值之后，还需要满足$a_i∣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)=ai(1≤i≤k)$验证。

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

---

Code

没想清楚细节WA了好几发

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
	t=0;int f=0;char c=getchar();
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

const int maxk=10000+5;
ll n,m;
int K;
ll X,Y;
ll a[maxk],r[maxk];

ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	ll xx,yy,re=exgcd(b,a%b,xx,yy);
	x=yy;
	y=xx-a/b*yy;
	return re;
}

ll excrt()
{
	ll M=a[1],R=r[1];
	for(register int i=2;i<=K;++i)
	{
		ll k1,k2,g=exgcd(M,a[i],k1,k2);
		if((r[i]-R)%g)return -1;
		k1=(r[i]-R)/g*k1%a[i];
		R+=k1*M;
		M=M/g*a[i];
		R%=M;
	}
	return (R-1+M)%M+1;
}

int main()
{
	read(n),read(m),read(K);
	read(a[1]),r[1]=0,X=a[1];
	for(register int i=2;i<=K;++i)
	{
		read(a[i]),r[i]=1-i;
		ll g=gcd(X,a[i]);
		X=X/g*a[i];
	}
	Y=excrt();
	if(X>n || Y+K-1>m || Y<1)
	{
		printf("NO");
		return 0;
	}
	for(register int i=1;i<=K;++i)
		if(gcd(X,Y+i-1)!=a[i])
		{
			printf("NO");
			return 0;
		}
	printf("YES");
	return 0;
}