A Horrible Poem （HYSBZ - 2795，字符串哈希 + 枚举最小循环节小技巧~）

一.题目链接：

HYSBZ-2795

二.题目大意：

给一个长度为 n 的字符串，q 次询问，每次问 s[l...r] 的最小循环节.

三.分析：

技巧一：字符串 s[l, r] 具有循环节 k 等价于 s[l, r - k] == s[l + k, r].

技巧二：线性筛中预处理出每个数的最小质因子，可  进行质因数分解. 

技巧三：字符串的最小循环节可通过对字符串长度的每个质因子通过试除法求解.

之前找最小循环节的时候我都是去枚举字符串长度的约数，逐一 check，时间复杂度 

考虑另一种方式，设 n 为字符串长度，ans 为最小循环节长度。

ans 的初始值不妨设为 n，即字符串自身是一个循环节.

对 n 进行质因子分解得到 

那么去检查  是否为循环节

若是，再去检查  是否为循环节 

否则，再去检查  是否为循环节.

四.代码实现：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int M = (int)5e5;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)19890907;
const ull base = 131;char s[M + 5];
ull p[M + 5];
ull f[M + 5];bool is_prime[M + 5];
int prime[M + 5], cnt;
int v[M + 5];//最小质因子void init()
{memset(is_prime, 1, sizeof(is_prime));is_prime[0] = is_prime[1] = 0;for(int i = 2; i <= M; ++i){if(is_prime[i]){prime[++cnt] = i;v[i] = i;}for(int j = 1; j <= cnt && i * prime[j] <= M; ++j){is_prime[i * prime[j]] = 0;v[i * prime[j]] = prime[j];if(i % prime[j] == 0){break;}}}
}ull cal(int l, int r)
{return f[r] - f[l - 1] * p[r - l + 1];
}bool check(int l, int r, int k)
{return cal(l, r - k) == cal(l + k, r);
}int main()
{init();int n; scanf("%d", &n);scanf("%s", s + 1);p[0] = 1; for(int i = 1; i <= n; ++i) p[i] = p[i - 1] * base;f[0] = 1; for(int i = 1; i <= n; ++i) f[i] = f[i - 1] * base + s[i] - 'a' + 1;int q; scanf("%d", &q);while(q--){int l, r; scanf("%d %d", &l, &r);int len = r - l + 1, ans = r - l + 1;while(len != 1){int t = v[len];while(len % t == 0) len /= t;while(ans % t == 0 && check(l, r, ans / t)) ans /= t;}printf("%d\n", ans);}return 0;
}