题解

做法

令两循环节分别为 。模拟题意，比较两字符串直到第 个字符为止。

证明

以下记号不区分串和串长

首先给出 Periodicity Lemma：

假设一个字符串 有循环节（不需要是完整循环节） 和 ，并且满足 ，那么 也是一个循环节。

证明见 张晴川知乎专栏
叉姐给出了一个数论证明

记由串 无限循环得到的串为 。记串 到第 位的前缀为 。令 ，。
当 时答案显然。下面证当 时，必有 ：
令 ，由 Periodicity Lemma， 存在循环节 ，并且它显然是 的一个完整循环节。
由此易得， 也是 的完整循环节，并且已经验证了 ，所以 。

时间复杂度

显然

代码

#include <bits/stdc++.h>

using namespace std;

const int N=100020;

char c1[N],c2[N];

char solve()
{
    int n=strlen(c1);
    int m=strlen(c2);

    for(int i=0;i<2*max(n,m);i++) //懒惰，直接*2了
    {
        if(c1[i%n]<c2[i%m]) return '<';
        else if(c1[i%n]>c2[i%m]) return '>';
    }
    return '=';
}

int main(void)
{    
    while(~scanf("%s",c1))
    {
        scanf("%s",c2);
        printf("%c\n",solve());
    }

    return 0;
}