题目链接：P3538 【POI2012】 OKR-A Horrible Poem

题意简介：给你一个字符串，并且有 $q$ 次询问，每一次询问给一段区间，问该字符串的这个区间中循环节最短的长度

应该很好理解了 你要是告诉我你不晓得循环节 那我也没得办法

$Example$：

8
aaabcabc
3
1 3
3 8
4 8

这是样例

在第一个询问中，询问区间 $1$ ~ $3$ 中的最短循环节。该字串为 $aaa$ ，显然最短循环节长度为 $1$

第二个询问，问区间 $3$ ~ $8$ 中最短循环节，即 $abcabc$ ，显然是 $3$

第三个询问，区间 $4$ ~ $8$，即 $bcabc$，这个就只能是 $5$ 啦

所以输出

1
3
5

所以应该怎样做呢？

$Hash$！

你别告诉我你不晓得哈希

不知道没关系，给你一个链接：P3370 【模板】字符串哈希

这里还需要知道一些哈希的基本操作，可以度娘自行搜索一下其他巨佬的博客，蒟蒻我在这里就不浪费时间啦

麻烦搞懂了哈希之后再往下看

为什么会想到哈希呢

因为哈希可以快速判断两个字串是否相同，而循环节正是一个连续重复出现的字串，并且本题只有一个字符串，只需做一次哈希即可

而这里我们需要判断一个子串是否为一个字符串的循环节，但如果一次次循环去判断，稍微有些慢了

所以这里扔一个快速判断的方法（用 $s[i][j]$ 表示串 $s$ 从第 $i$ 到第 $j$ 位）

若要判断该串的 $s[1][len]$ 这个字串是循环节，只需要 $s[1][r - len] == s[1 + len][r]$ 即可

那每次都暴力枚举每一个长度吗？$NO NO NO$

实际上，当一个串长 $len$ 时，其循环节循环次数一定是 $len$ 的约数 太显然了

注意上面是循环节循环次数！！！不是循环节长度 请勿搞混

并且，当这个串中间每个字母分别出现 $C_i$ 次的时候，循环节循环次数必须是 $gcd$($len$，$C_a$,$C_b$.....,$C_z$) 的约数，因为每一种字母出现的次数必须可以平均分在每一个循环节中

那么这样就很简单了，只要用前缀和维护一下区间内字符个数即可

自认为讲得很清楚了，上代码

// luogu-judger-enable-o2 //不要脸的O2
//Code By CXY
#include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;

#define ll unsigned long long

const int MAXN = 5e5 + 10;
const int base = 131;
const int INF = 1e9;

int n,q;
int f[MAXN][27];
char c[MAXN];
ll hash[MAXN],ans = INF;
ll power[MAXN];

template <typename T> inline void read(T &a) {
    a = 0;char c = getchar();int f = 1;
    while(!isdigit(c)) {if(c == '-') f = -1;c = getchar();}
    while(isdigit(c)) {a = (a << 3) + (a << 1) + (c ^ 48);c = getchar();}
    a *= f;
} // 快读

inline void Get_Hash() {
    power[0] = 1;
    for(register int i = 1;i <= n; ++i)
        power[i] = power[i - 1] * base;
    for(register int i = 1;i <= n; ++i)
        hash[i] = hash[i - 1] * base + (c[i] - 'a' + 1);
} // 哈希初始化

inline void Getf() {
    for(register int i = 1;i <= n; ++i) {
        for(register int j = 1;j <= 26; ++j)
            f[i][j] = f[i - 1][j];
        f[i][c[i] - 'a' + 1]++; 
    }
}//前缀和 可以快速求出一个子串中间每个字母出现的个数

ll gcd(ll x,ll y) {
    if(y == 0) return x;
    return gcd(y,x % y);
} //你别告诉我你不会求gcd

inline ll Getval(ll l,ll r) {return (hash[r] - hash[l - 1] * power[r - l + 1]);} //哈希基本操作 得到一个字串的哈希值 记得要乘上幂
inline ll Getnum(ll l,ll r,ll k) {return f[r][k] - f[l - 1][k];} //找一个字母k在字串l~r中间出现的次数

inline void update(ll l,ll r,ll len) {
    if(Getval(l,r - len) == Getval(l + len,r)) //快速判断是否为循环节
        ans = min(ans,len); //更新答案
} //判断+修改函数

inline void Doit() {
    int x,y;
    read(x);read(y);
    ll vgcd = y - x + 1;ans = INF;//vgcd一开始设为串长 即为循环节循环次数
    for(register int i = 1;i <= 26; ++i)
        vgcd = gcd(vgcd,Getnum(x,y,i)); //对每一个字母的出现次数取gcd
    for(register int i = 1;i * i <= vgcd; ++i) {//枚举循环次数
        if(vgcd % i) continue; //循环次数必须是vgcd的约数
        update(x,y,(y - x + 1) / i);//注意！当循环次数为i时，循环节长度为((y - x + 1) / i)
        update(x,y,((y - x + 1) / (vgcd / i)));//同样枚举循环次数为(vgcd / i)的情况
    }
    printf("%lld\n",ans);
}

int main () {
    read(n);
    gets(c + 1);
    Get_Hash(); Getf();
    read(q);
    while(q--) Doit();//每次询问就进行一次操作
    return 0;//华丽地结束
}

就这样 水掉了 做完了一道紫题，其实理一下这道题中间哈希只是帮助 数论才是精髓

初二的 $OIer$ ，请多关照