Codeforces #207 Div1. B. Xenia and Hamming

さてB。size_tが32bitだということを知らずにオーバーフローした…。
http://codeforces.com/contest/356/problem/B

問題

文字列XとN回繰り返したものと文字列YをM回繰り返したものがある。
両者の長さは同じである。
両文字列のうち同じインデックスの文字が異なる個数を答えよ。

解法

文字列の長さが10^6以下、N<=10^12なので、全体では10^18位の数になる。

XとYの長さをXL,YLとし、そのの最大公約数とGとすると、i%G==j%Gとなるi,jについてX[i]とY[j]が比較される可能性がある。
これらの不一致回数を数えればよい。
両文字列の長さをfor文で回すとXL*YLの時間がかかるTLEするので、各i%G==j%G==pとなるi,jにおいてa～zの登場回数を数え、全体から一致数を引けばよい。
つまり(XL/G)*(YL/G)から、(X[i]=='a')の数と(Y[j]=='a')の積を引く、という処理を'a'～'z'について同様に行う。

ll N,M;
string X,Y;
ll XL,YL;
ll cand[2][26];

void solve() {
	int f,i,j,k,l,r, x,y;
	
	cin>>N>>M>>X>>Y;
	XL=X.size();
	YL=Y.size();
	ll G=XL*YL/__gcd(XL,YL);
	ll LG=XL*N/G;
	N/=LG;
	M/=LG;
	
	ll szg = __gcd(X.size(),Y.size());
	ll ret = X.size()*(ll)Y.size()/szg;
	FOR(i,szg) {
		ZERO(cand[0]);
		ZERO(cand[1]);
		for(j=i;j<X.size();j+=szg) cand[0][X[j]-'a']++;
		for(j=i;j<Y.size();j+=szg) cand[1][Y[j]-'a']++;
		FOR(j,26) ret-=cand[0][j]*cand[1][j];
	}
	cout << ret*LG << endl;
}

まとめ

普段64bit環境でコードを書いていて、size_t==long==64bitと勘違いした…。