Codeforces 338D GCD Table 中国剩余定理

主题链接：点击打开链接

特定n*m矩阵，[i,j]分值为gcd(i,j)

给定一个k长的序列，问能否匹配上矩阵的某一行的连续k个元素

思路：

我们要求出一个解(i,j) 使得 i<=n && j<=m 此时输出 YES

对于j

j % b[0] = 0

j+1 % b[1] = 0

···

j+l % b[l] = 0

依据定理：若 a == b (mod n) => (a+c) == b+c (mod n)

所以将上式变换为

j % b[0] = 0

j % b[1] = -1

···

j % b[n-1] = - (n-1)

最后求出的i,j 检验一下是否满足 gcd(i,j+k) == input[k];

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define ll __int64
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a%b);
}
void extend_gcd (ll a , ll b , ll& d, ll &x , ll &y) {  
	if(!b){d = a; x = 1; y = 0;}
	else {extend_gcd(b, a%b, d, y, x); y-=x*(a/b);}
}
ll china(ll l, ll r, ll *m, ll *a){ //下标[l,r] 方程x%m=a;
	ll lcm = 1;
	for(ll i = l; i <= r; i++)lcm = lcm/gcd(lcm,m[i])*m[i];
	for(ll i = l+1; i <= r; i++) {
		ll A = m[l], B = m[i], d, x, y, c = a[i]-a[l];
		extend_gcd(A,B,d,x,y);
		if(c%d)return -1;
		ll mod = m[i]/d;
		ll K = ((x*c/d)%mod+mod)%mod;
		a[l] = m[l]*K + a[l];
		m[l] = m[l]*m[i]/d;
	}
	if(a[l]==0)return lcm;
	return a[l];
}
#define N 10005
ll n[N],b[N],tmp[N],len,nn,mm;
bool work(){
	memset(b, 0, sizeof b);
	memcpy(tmp,n,sizeof n);
	ll i = china(1,len,n,b);
	if(i>nn || i<=0)return false;
	for(ll hehe = 1; hehe <= len; hehe++)b[hehe] = -hehe+1;
	memcpy(n,tmp, sizeof n);
	ll j = china(1,len,tmp,b);
	if(j+len-1>mm || j<=0)return false;
	for(ll hehe = 1; hehe <= len; hehe++)if(gcd(i,j+hehe-1)!=n[hehe])return false;
	return true;
}
int main(){  
	while(cin>>nn>>mm>>len){
		for(ll i = 1; i <= len; i++) cin>>n[i];
		work()?
puts("YES"):puts("NO");
	}
	return 0;  
}