ひたすら面倒な問題。
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; }
まとめ
これは本番では出しにくいよなぁ…。