这道题有个比较nice的思路。
设两个字符串长度的最小公倍数为lcm，最大公因数为gcd.
那么for(int i=0;i<len1;i++) vis[i%gcd][a[i]-'a']++;
for(int i=0;i<len2;i++) calc+=vis[i%gcd][b[i]-'a'];就能够统计lcm内相同的字符的个数，不同的就是lcm-calc；
在lcm内会跑完所有的gcd匹配情况，所以能够如此快速统计。细细感悟一下，，
比如说这里以4的红圈圈为例，那么它会依次匹配完6的红勾勾，然后完成匹配....tql
上代码:
1 #include<bits/stdc++.h> 2 #define maxn 1000005 3 using namespace std; 4 string a,b; 5 typedef long long ll; 6 ll n,m; 7 ll gcd(ll x,ll y){ 8 if(y==0) return x; 9 else return gcd(y,x%y); 10 } 11 ll vis[maxn][30]; 12 void init(){ 13 scanf("%lld%lld",&n,&m); 14 cin>>a; 15 cin>>b; 16 ll len1=a.length(),len2=b.length(); 17 ll t=gcd(len1,len2); 18 ll lcm=len1*len2/t; 19 /*string c=a; 20 for(int i=1;i<t/len1;i++) a+=c;//粘贴 21 c=b; 22 for(int i=1;i<t/len2;i++) b+=c;*///竟然会MLE 23 ll calc=0; 24 for(int i=0;i<len1;i++) vis[i%t][a[i]-'a']++; 25 for(int i=0;i<len2;i++) calc+=vis[i%t][b[i]-'a']; 26 calc=lcm-calc; 27 ll cnt=n/(lcm/len1); 28 printf("%lld",cnt*calc); 29 } 30 int main(){ 31 init(); 32 33 return 0; 34 }