Description：

给定两个字符串，分别复制 $n,m$ 倍，保证最后长度相同，问有几个字符对应相等。

$1\leqslant n,m \leqslant10^9,1\leqslant|S|,|T|\leqslant 10^6$

Solution：

首先假设 $\gcd(|S|,|T|)=1$ ，那么发现由于互质的两个数某个数的倍数会遍历另一个数的剩余系，所以 $|S|$ 中的每个字符都会和 $|T|$ 中的字符匹配一下，所以开个桶记录 $|S|$ 的每个字符出现次数再枚举 $|T|$ 的每个字符累加答案，如果 $\gcd$ 不为 $1$ ，那么可以看成是很多长为 $\gcd$ 的段，每一段都会互相遍历一次，所以开一个 $n\times26$ 的桶记录每个字符 $\%gcd$ 的值，用桶记录一下，然后还是用第二个串累加答案就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXL 1000010

char S[MAXL],T[MAXL];

int Sl,Tl;

long long len;

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

int cnt[MAXL][26];

int main()

{

	freopen("string.in","r",stdin);

	freopen("string.out","w",stdout);

	scanf("%d%d",&n,&m);

	scanf("%s%s",S + 1,T + 1);

	Sl = strlen(S + 1);Tl = strlen(T + 1);

	len = (long long)Sl * n;

	int g = gcd(Sl,Tl);

	long long ans = 0;

	for(int i = 1;i <= Sl;++i)++cnt[i % g][S[i] - 'a'];

	for(int i = 1;i <= Tl;++i)ans += cnt[i % g][T[i] - 'a'];

	cout << ans * (len / (long long)((long long)Sl / g * Tl)) << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}