Codeforces #196 Div1 D. GCD Table

CF196のDiv1Dは比較的落ち着いた難易度。
http://codeforces.com/contest/338/problem/D

問題

N行M列のテーブルがあり、i行j列の要素G(i,j)はiとjの最大公約数である。

ここにK要素の数列A[i]が与えられる。
数列Aと一致する部分列を含む行はG中に存在するか。

解法

A[0]がG(i,j)と一致すると仮定する。
まずiはAの最小公倍数の倍数でなければならない。
iを不必要に大きくする必要はないので、iはAの最小公倍数に定める。
(このとき、i＞Nなら条件を満たす行は存在しない。)

ここで、AよりG(i,j)は以下を満たさなければならない。

• GCD(i, (j+0)) = A[0] ⇒ (j+0) % A[0] == 0
• GCD(i, (j+1)) = A[1] ⇒ (j+1) % A[1] == 0
• ...
• GCD(i, (j+(K-1))) = A[K-1] ⇒ (j+(K-1)) % A[K-1] == 0

あとは上記条件より、中国人剰余定理でjを求め、1≦j≦Mのものが存在するかチェックすればよい。

ll N,M,K;
ll A[100001];

ll ext_gcd(ll p,ll q,ll& x, ll& y) { // get px+qy=gcd(p,q)
	if(q==0) return x=1,y=0,p;
	ll g=ext_gcd(q,p%q,y,x);
	y-=p/q*x;
	return g;
}

pair<ll,ll> cmt(ll a1,ll mo1,ll a2,ll mo2) { // return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2
	ll g,x,y,z;
	g=ext_gcd(mo1,mo2,x,y);
	a1=(a1%mo1+mo1)%mo1;a2=(a2%mo2+mo2)%mo2;
	if(a1%g != a2%g) return pair<ll,ll>(-1,0); // N/A
	ll lcm=mo1*(mo2/g);
	if(lcm<mo1) return pair<ll,ll>(-2,0); // overflow
	//ll v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g);
	ll t=1000000;
	ll v=((a2-a1)%lcm+lcm)*t%lcm;
	x=(x%lcm+lcm)%lcm;
	v=v*(x/t)+((a2-a1)%lcm+lcm)*(x%t);
	v=v%lcm;
	v=(v*t)%lcm*(mo1/g/t)+v*(mo1/g%t)%lcm+a1;
	v=v%lcm+lcm;
	v%=lcm;
	return make_pair(((v%lcm)+lcm) % lcm,lcm);
}

void solve() {
	int i,j,k,l,r; string s;
	
	cin>>N>>M>>K;
	
	ll G=1,C=0,TG=1;
	FOR(i,K) {
		cin>>A[i];
		ll ng=TG*(A[i]/__gcd(TG,A[i]));
		if(ng<TG || ng>N) return _P("NO\n");
		TG=ng;
		
		//_P("%d %lld %lld %lld %lld\n",i,A[i],C,G,(A[i]-i%A[i])%A[i]);
		//_P("+%lld\n",A[i]);
		pair<ll,ll> p=cmt(C,G,(A[i]-i%A[i])%A[i],A[i]);
		C=p.first;
		if(C<0) return _P("NO\n");
		G=p.second;
		//_P("%d %lld %lld %lld\n",i,A[i],C,G);
	}
	if(C==0) C=G;
	if(C+(K-1)>M) return _P("NO\n");
	
	FOR(i,K) if(__gcd(C+i,G)!=A[i]) return _P("NO\n");
	_P("YES\n");
	
}

まとめ

中国人剰余定理を解けばよいと書いたけど、実際この定理に則ったコード書くのにかなりバグ埋め込んだりして苦労した。
おかげで今回中国人剰余定理のライブラリができた。