Codeforces Round #207 (Div. 1) B. Xenia and Hamming
解法
x と y の文字列の長さを求めます。で, その最小公倍数を求めます。その値が g であったとすると, x の i+a*g (0 <= i < g, i+a*g < x.size()) にある文字は, y の i+b*g (i+b*g < y.size()) にある文字とのみ必ずマッチします。また, i+a*g にある文字がは, i+b*g にあるそれぞれの文字と, 何回マッチするかもわかります(すべて等しい数になる)。
なので, それらの値を足し算して求めれば良いです。
const int MAXN = 1000010; int alpha[MAXN][26]; int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, m; cin >> n >> m; string x, y; cin >> x; cin >> y; int a = x.size(), b = y.size(); int g = __gcd(a, b); for (int i = 0; i < g; i++) { for (int j = i; j < a; j+=g) { alpha[i][x[j]-'a']++; } } ll ans = 0; for (int i = 0; i < b; i++) { ll sum = a/g - alpha[i%g][y[i]-'a']; ans += sum; } ll num = m/(a/g); ans *= num; cout << ans << endl; return 0; }