2020牛客暑期多校训练营（第一场）F Infinite String Comparision两个字符串循环节结论

虽然把最长的扩大两倍，然后那短的依次去比较就能过，但还是记录一下结论。

By the Periodicity Lemma, if there is no mismatches in the first a + b - gcd(a, b) characters, the two string are identical

也就是两个由长度分别为a,b进行无限循环的字符串，如果它们前a+b-gcd(a,b)个字符相同，那么它们就是相同的。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+11;
char a[N],b[N];
int solve(){
    int la=strlen(a),lb=strlen(b),len=la+lb-__gcd(la,lb);
    for(int i=0;i<len;i++){
        if(a[i%la]>b[i%lb]) return 1;
        else if(a[i%la]<b[i%lb]) return -1;
    }
    return 0;
}
int main(){
    while(~scanf("%s%s",a,b)){
        int flag=solve();
        if(flag==0) printf("=
");
        else if(flag==1) printf(">
");
        else printf("<
");
    }
    return 0;
}