Codeforces ECR #016 : D. Two Arithmetic Progressions

ひたすら面倒な問題。
http://codeforces.com/contest/710/problem/D

問題

2つの関数f(k)=a1*k+b1, g(l)=a2*l+b2がある。
L≦x≦Rの範囲の整数xで、f(k)=g(l)=xとなる整数k,lの組がいくつあるかも求めよ。

解法

f(k)やg(l)の取り得る値はそれぞれ(R-L)/a1・(R-L)/a2通り程度なので、a1かa2が大きいならf(k)やg(l)を列挙してしまおう。
a1,a2が共に小さいなら、LCM(a1,a2)も余り大きくないので周期を求めよう。

色々コーナーケースがあるので注意。

ll A1,B1,A2,B2,L,R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A1>>B1>>A2>>B2>>L>>R;
	L=max(L,max(B1,B2));
	if(L>R) return _P("0\n");
	
	if(A2==0) swap(A1,A2),swap(B1,B2);
	if(A1==0) {
		if(A2==0) return _P("%d\n", (B1==B2));
		return _P("%d\n",(B1>=B2) && ((B1-B2)%A2==0));
	}
	
	if(A2>=1000) swap(A1,A2),swap(B1,B2);
	if(A1>=1000) {
		ll ret=0;
		for(ll x=0;A1*x+B1<=R;x++) {
			if(A1*x+B1<L) continue;
			ll X=A1*x+B1 - B2;
			if(X%A2) continue;
			if(X/A2>=0) ret++;
		}
		cout<<ret<<endl;
		return;
	}
	
	FOR(i,1000001) {
		if(B1<L) B1 += (L-B1+A1-1)/A1*A1;
		if(B2<L) B2 += (L-B2+A2-1)/A2*A2;
		L=max(L,max(B1,B2));
		if(B1==L && B2==L) break;
	}
	if(i==1000001 || L>R) return _P("0\n");
	ll lcm=A1*A2/__gcd(A1,A2);
	cout<<(R-L)/lcm+1<<endl;
	
	
}

まとめ

これは本番では出しにくいよなぁ…。