题干：
Xenia is an amateur programmer. Today on the IT lesson she learned about the Hamming distance.
The Hamming distance between two strings s = s1s2... sn and t = t1t2... tn of equal length n is value . Record [si ≠ ti] is the Iverson notation and represents the following: if si ≠ ti, it is one, otherwise — zero.
Now Xenia wants to calculate the Hamming distance between two long strings a and b. The first string a is the concatenation of n copies of string x, that is, . The second string b is the concatenation of m copies of string y.
Help Xenia, calculate the required Hamming distance, given n, x, m, y.
Input
The first line contains two integers n and m (1 ≤ n, m ≤ 1012). The second line contains a non-empty string x. The third line contains a non-empty string y. Both strings consist of at most 106 lowercase English letters.
It is guaranteed that strings a and b that you obtain from the input have the same length.
Output
Print a single integer — the required Hamming distance.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
Examples
Input
100 10 a aaaaaaaaaa
Output
0
Input
1 1 abacaba abzczzz
Output
4
Input
2 3 rzr az
Output
5
Note
In the first test case string a is the same as string b and equals 100 letters a. As both strings are equal, the Hamming distance between them is zero.
In the second test case strings a and b differ in their 3-rd, 5-th, 6-th and 7-th characters. Thus, the Hamming distance equals 4.
In the third test case string a is rzrrzr and string b is azazaz. The strings differ in all characters apart for the second one, the Hamming distance between them equals 5.
题目大意：
给出一个n，m 然后给出两个串的循环节S和T(不一定等长)， n代表第一个串有多少次循环，m代表第二个串有多少次循环，问两个串的Hamming distance是多少，这个距离是指对应位置的字符如果相等对结果的贡献就是0，否者就是1。(加长的两个字符串等长)
解题报告：
这是一道关于汉明距离的题目。首先涨一波知识：
这题第一眼应该就跟数论gcd，lcm相关（因为循环节和循环次数嘛最后还等长），而且数据量就知道不可能让你暴力，肯定是有重复计算，我们需要算那个最小的然后扩大相应的倍数。
于是首先想到只要比较了两个串的lcm长度，再扩大相应倍数就可以，但是这样的数据量还是会TLE，想想也知道啊，如果len1和len2互质的话，复杂度O(len1*len2)，最坏为10^12。
想办法优化：
分析一下会发现，在上面的想法中，有一部分比较是没有必要的，比如：
S: abacdcde T: acdaed
S的长度为8，T的长度为6，len1与len2的gcd = 2，lcm = 24。
比较时
T开头的a并不是和S中的每一位都能进行比较的，也就是说，在一个循环结中，可以一次性将T中的每一位与其将会与S中所对应的位置的字符都比较一下，也就是预处理出来。也不难发现，T的第一个字符，总与s[1]+k*gcd比较，第二个字符，总与s[2]+k*gcd比较...以此类推。（假设从s[1]为第一个字符而不是s[0]）
设g=gcd(len1,len2)，设ans为S和T中对应位置相同的字符的数目，方法就是在i from 0 to gcd(len1,len2)-1 的循环中，将S分为g个小段，每段长度为len1/g，统计每次该小段上第i个字符出现的次数，然后将T中g个小段的第i个字符出现的次数加入到ans中。最后将ans扩大相应倍数，然后再用总的长度减去ans就是答案。
AC代码1：（这是一个网络的代码，但是因为dpa数组开成了longlong，所以MLE了，下面有一个优化版本）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int qq = 1e6+10;
char a[qq],b[qq];
int dpa[qq][27],dpb[qq][27];
ll gcd(ll a, ll b){
return b==0?a:gcd(b, a%b);
}
ll lcm(ll a, ll b){
return a/gcd(a, b)*b;
}
int main(){
ll n,m;scanf("%lld%lld",&n,&m);
scanf("%s%s",a,b);
ll lena = strlen(a);
ll lenb = strlen(b);
ll g = gcd(lena, lenb);
ll l = lena/g*lenb;
memset(dpa, 0, sizeof(dpa));
memset(dpb, 0, sizeof(dpb));
for(int i=0; i<lena; ++i) dpa[i%g][a[i]-'a']++;
for(int i=0; i<lenb; ++i) dpb[i%g][b[i]-'a']++;
ll ans = 0;
for(int i=0; i<g; ++i)
for(int j=0; j<26; ++j)
ans+=(ll)dpa[i][j]*dpb[i][j];
ans = n*lena/l*ans; //每一个长度为l的字符串中，所含相同的字符有ans个、
// 求长度为n*lena/l 个长度为l的字符串中，所含相同字符的总数、
ans = n*lena - ans; //求反面、 然后用总长度减去相同字符的个数、
printf("%lld\n", ans);
return 0;
} AC代码2：（这样不需要二维数组，时间慢了一丢丢200+ms，但是剩下了很多空间复杂度）
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e6 + 5;
char s1[MAX],s2[MAX];
ll cnt[50];
ll Gcd(ll a,ll b) {
while(a^=b^=a^=b%=a);
return b;
}
int main()
{
ll n,m;
cin>>n>>m;
cin>>s1>>s2;
ll len1 = strlen(s1);
ll len2 = strlen(s2);
ll gcd = Gcd(len1,len2);
ll lcm = len1 * (len2 / gcd);
ll l1=len1/gcd,l2=len2/gcd;
ll ans = 0;
for(ll i = 0; i<gcd; i++) {
memset(cnt,0,sizeof cnt);
for(ll j = 0; j<l1; j++) {
cnt[s1[gcd*j + i]-'a'] ++;
}
for(ll j = 0; j<l2; j++) {
ans += cnt[s2[gcd*j+i]-'a'];
}
}
ans *=len1*n/ lcm ;
// ans *= (m*gcd)/len1;
ans = len1*n-ans;
printf("%lld\n",ans);
return 0 ;
} 总结：
这题用的思维主要是：
1.求问题的反面。
2.cnt数组运用了桶计数的思想。空间换时间，1e6正好也开的下（对这个数字还是不太敏感啊你、、）（不对这题好像不是那个桶计数，，，这题cnt数组就开27 就够了）
京公网安备 11010502036488号