mayoko’s diary

プロコンとかいろいろ。

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;
}