Codeforces Round #207 (Div. 1) B. Xenia and Hamming(gcd的运用)

题目链接: B. Xenia and Hamming

题意: 要求找到复制后的两个字符串中不同样的字符

思路: 子问题: 在两串长度是最大公倍数的情况下, 求出一个串在还有一个串中反复字符的个数

CODE:

#include <iostream>
#include<stdio.h>
#include<string>
#include<string.h>
using namespace std;
#define M 1000006
int com[M][26];
int gcd(int a,int b)
{
    return b==0?
a:gcd(b,a%b);
}
int main()
{
    long long n,m;
    string x,y;
    while(~scanf("%I64d%I64d",&n,&m))
    {
        cin>>x>>y;
        memset(com,0,sizeof(com));
        int lenx=x.size(),leny=y.size();
        long long g=gcd(lenx,leny);
        long long ans=lenx/g*leny;
        long long a=ans;
        for(int i=0;i<lenx;i++)      //巧妙的处理~将两串中反复的字符储存起来
            com[i%g][x[i]-'a']++;
        for(int i=0;i<leny;i++)
            ans-=com[i%g][y[i]-'a'];
        printf("%I64d
",ans*(n*lenx/a));
    }
    return 0;
}