题目大意
给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。
如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。
输入格式
第一行一个正整数 n，表示 S 的长度。
第二行 n 个小写英文字母，表示字符串 S 。
第三行一个正整数 q ，表示询问个数。
下面 q 行每行两个正整数 a,b，表示询问字符串 S[a..b] 的最短循环节长度。
输出格式
依次输出 q 行正整数，第 i 行的正整数对应第 i 个询问的答案。
输入样例
8
aaabcabc
3
1 3
3 8
4 8
输出样例
1
3
5
数据范围
1≤a≤b≤n≤5×10^5 , q≤2×10^5。
题解
容易想到，对于每一个子串，我们要枚举其循环节，而循环节的长度一定是子串长度的因子。所以关键是枚举出对于每一个数的所有因子。
对于每个子串，用$O(\sqrt{n}) $的朴素枚举显然会TLE。所以我们要换一种枚举方法。
我们先欧拉筛求出$1... n$的所有质数，根据欧拉筛的枚举顺序，我们也可以顺便求出任意一个数$i$的最小质因子$mp[i]$。
枚举出这个有什么用呢？其实我们可以根据这个求出任意长度$len$的所有质因子。
我们用$t[i]$表示$len$的第$i$个质因子，我们不断记录$mp[len]$，然后让$len = \frac{len}{mp[len]}$，直到$len = 1$为止。此时我们就可以得到$len$的$cnt$个质因子$t[1...cnt]$，且有$t[i] \leqslant t[i + 1]$。
我们设最短循环节的长度为$len$。最开始我们然后$len$等于子串长度。
然后我们从$t[1]$开始枚举$t[i]$，我们先让$len = \frac{len}{t[i]}$，然后判断此时的$len$是否是循环节长度，如果不是，则再让$len$乘回$t[i]$。判断完后继续枚举$t[i]$即可。这样我们就可以不断得到越来越小的循环节长度，直到得到答案。
#include <iostream>
#include <cstdio>
#include <cctype> #define MAX_N (500000 + 5) #define SIZE (1 << 21) #define Getchar() (pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, SIZE, stdin), pr1 == pr2) ? EOF : *pr1++)
#define Putchar(ch) (pw < SIZE ? fw[pw++] = (ch) : (fwrite(fw, 1, SIZE, stdout), fw[(pw = 0)++] = (ch))) using namespace std; char fr[SIZE], * pr1 = fr, * pr2 = fr;
char fw[SIZE];
int pw; int Read()
{
int res = , sign = ;
char ch = Getchar();
while(!isdigit(ch))
{
if(ch == '-') sign = -;
ch = Getchar();
}
while(isdigit(ch))
{
res = res * + ch - '';
ch = Getchar();
}
return res * sign;
} void Write(int val)
{
char a[];
int len = ;
if(val < )
{
val = -val;
Putchar('-');
}
do
{
a[++len] = val % + '';
val /= ;
}
while(val);
while(len)
{
Putchar(a[len--]);
}
return;
} typedef unsigned long long ull;
typedef const unsigned long long cull;
int n;
char s[MAX_N];
cull b = ;
ull h[MAX_N], pb[MAX_N];
int p[MAX_N], mp[MAX_N], tot; void Euler()
{
for(register int i = ; i <= n; ++i)
{
if(!mp[i]) p[++tot] = mp[i] = i;
for(register int j = ; i * p[j] <= n; ++j)
{
mp[i * p[j]] = p[j];
if(!(i % p[j])) break;
}
}
return;
} void Hash()
{
pb[] = ;
for(register int i = ; i <= n; ++i)
{
h[i] = h[i - ] * b + s[i] - 'a' + ;
pb[i] = pb[i - ] * b;
}
return;
} ull Value(int lt, int rt)
{
return h[rt] - h[lt - ] * pb[rt - lt + ];
} int main()
{
n = Read();
for(register int i = ; i <= n; ++i)
{
s[i] = Getchar();
}
Euler();
Hash();
int q, lt, rt;
q = Read();
int t[MAX_N], cnt, len;
while(q--)
{
lt = Read();
rt = Read();
len = rt - lt + ;
cnt = ;
while(len > )
{
t[++cnt] = mp[len];
len /= mp[len];
}
len = rt - lt + ;
for(register int i = ; i <= cnt; ++i)
{
len /= t[i];
if(Value(lt, rt - len) != Value(lt + len, rt)) len *= t[i];
}
Write(len);
Putchar('\n');
}
fwrite(fw, , pw, stdout);
return ;
}
参考程序