Codeforces 356B - Xenia and Hamming

問題 : Xenia and Hamming

概要 :

文字列$x$ を$n$ 回繰り返した文字列$a$ と, 文字列$y$ を$m $ 回繰り返した文字列$b$ がある.

$a$ と$b$ のハミング距離を求めよ. ただし, ハミング距離とは$\displaystyle \sum_{i=1}^{n} [a_i \neq b_i]$ で定義され, $a_i = b_i$ なら$[a_i \neq b_i] = 0$, $a_i \neq b_i$ なら$[a_i \neq b_i] = 1$ とする.

$1 \leqq n,\ m \leqq 10^{12}$
$1 \leqq |x|,\ |y| \leqq 10^6$
$n|x| = m|y|$
文字列は英小文字からのみ成る.

解法 :

それぞれの文字列は$\gcd(|x|,\ |y|)$ ごとにグループに分かれ, それぞれのグループの間の文字の組み合わせはすべて掛け合わされる. よって, $\gcd(|x|, \ |y|)$ ごとに文字の出現頻度を数えて, 幾つの文字が等しくなるかを調べて全体から引けば良い.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long lint;

lint gcd(lint x, lint y)
{
	if (x < y) swap(x, y);
	return (!y ? x : gcd(y, x % y));
}

lint lcm(lint x, lint y)
{
	return (x / gcd(x, y) * y);
}

int ctx[1000001][26], cty[1000001][26];

int main()
{
	lint m, n, lx, ly;
	static char x[1000001], y[1000001];
	
	scanf("%lld %lld", &m, &n);
	scanf("%s", x);
	scanf("%s", y);
	
	lx = strlen(x); ly = strlen(y);
	lint g = gcd(lx, ly);
	
	for (int i = 0; x[i]; i++) ctx[i % g][x[i] - 'a']++;
	for (int i = 0; y[i]; i++) cty[i % g][y[i] - 'a']++;
	
	lint same = 0;
	
	for (int i = 0; i < g; i++){
		for (int j = 0; j < 26; j++){
			same += (lint)ctx[i][j] * cty[i][j];
		}
	}
	
	same = same * (lx * m / lcm(lx, ly));
	
	lint ans = lx * m - same;
	
	printf("%lld\n", ans);
	
	return (0);
}