询问循环节的“模板题”?
首先，有一个经典结论：若存在一长度为 \(len\) 的循环节，则 \(s[l \sim r-len]=s[l+len \sim r]\)，简单来说就是利用移位，说明是否是循环节。
有了这个结论，再使用字符串哈希，我们就可以做到 \(O(1)\) 判断。
因为：字符串长度=循环节长度 \(\times\) 循环次数。
所以我们要么枚举循环节长度，要么枚举循环次数。两个都得是字符串长度的因数。
如果枚举循环节长度，考虑先预处理出所有长度的因数，时间为 \(O(n\log n)\)，每次查询最坏的可能是 \(O(q \sqrt n )\)，最坏情况下无法通过。
而循环节长度显然是不好优化的，因为如果长度为 \(1\) 的不行，不能说明长度为 \(2\) 的不行。而我们要求最短循环节，所以只能从小到大枚举，不利于优化。
考虑枚举循环次数（转化为求循环次数最大），若循环次数为 \(3\) 的不行，那么循环次数为 \(6,9,12...\) 的肯定也不行。
于是我们将长度质因数分解，对于每个质因数，如果除完之后可以，那么我们就除，用筛法记录下每个数字的最小质因子方便快速分解。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=5e5+10,M=5e5;
const LL MOD1=1e9+7,MOD2=998244353,base=13331;
int n,q;
LL p1[N],p2[N],h1[N],h2[N];
string s;
int f[N],fac[N];
void init() {
for(int i=2;i<=M;i++) {
if(f[i]) continue;
for(int j=1;j*i<=M;j++) {
if(!fac[i*j]) fac[i*j]=i;
f[i*j]=1;
}
}
}
LL get1(int l,int r) {
return ((h1[r]-h1[l-1]*p1[r-l+1])%MOD1+MOD1)%MOD1;
}
LL get2(int l,int r) {
return ((h2[r]-h2[l-1]*p2[r-l+1])%MOD2+MOD2)%MOD2;
}
int main() {
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
init();
cin>>n>>s;
s=" "+s;
p1[0]=p2[0]=1;
for(int i=1;i<=n;i++) {
p1[i]=p1[i-1]*base%MOD1;
p2[i]=p2[i-1]*base%MOD2;
h1[i]=(h1[i-1]*base+s[i]-'a')%MOD1;
h2[i]=(h2[i-1]*base+s[i]-'a')%MOD2;
}
cin>>q;
while(q--) {
int l,r; l=read(); r=read();
int len=r-l+1,ans=r-l+1;
while(len>1) {
if(get1(l,r-ans/fac[len])==get1(l+ans/fac[len],r)) {
ans/=fac[len];
}
len/=fac[len];
}
cout<<ans<<'\n';
}
return 0;
}
*/