Codeforces #305 Div1 A. Mike and Frog

ABCしか解いてないけどHackのおかげで割と好順位だった。
http://codeforces.com/contest/547/problem/A

問題

整数Mと、H[i],A[i],X[i],Y[i]が２組与えられる。
1秒毎にH[i]=(X[i]*H[i]+Y[i])%MでH[i]が更新される。
H[0]==A[0]かつH[1]==A[1]となる最短時間を求めよ。

解法

時間が経過すると、いずれH[i]は周期的に遷移するようになる。
よって2*M秒位まで愚直にシミュレーションしてH[i]==A[i]となる周期を求め、そこからH[0]とH[1]が条件を満たす最小の時刻を求めればよい。

int M;
ll H[2],A[2];
ll X[2],Y[2];
ll fir[2],sec[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M;
	FOR(i,2) cin>>H[i]>>A[i]>>X[i]>>Y[i];
	FOR(i,2) {
		fir[i]=sec[i]=-1;
		FOR(j,2000100) {
			H[i]=(X[i]*H[i]+Y[i])%M;
			
			if(H[i]==A[i]) {
				if(fir[i]==-1) fir[i]=j+1;
				else {
					sec[i]=j+1;
					break;
				}
			}
		}
	}
	if(fir[0]==-1 || fir[1]==-1) return _P("-1\n");
	
	ll per=(sec[0]==-1)?0:(sec[0]-fir[0]);
	ll per2=(sec[1]==-1)?0:(sec[1]-fir[1]);
	
	FOR(i,2000100) {
		ll tim=fir[0]+per*i;
		bool ok=false;
		if(per2==0) ok=tim==fir[1];
		else ok=(tim>=fir[1] && (tim-fir[1])%per2==0);
		
		if(ok) {
			cout<<tim<<endl;
			return;
		}
	}
	_P("-1\n");
}

まとめ

ここらへんはまだ簡単。