题解 P3538 【[POI2012]OKR-A Horrible Poem】

题目要求给出一个字符串和q次询问，并求出每次询问的区间内的最短循环节长度 首先有几个性质 1、循环节一定是长度的约数 2、如果n是一个循环节，那么k*n也必定是一个循环节（关键所在） 3、n是[l,r]这一段的循环节 的充要条件是 [l,r-n]和[l+n,r]相同（利用这个性质我们在判断是否为循环节是可以做到O(1)） 所以我们可以在求出这个区间的长度之后，判断它的每个约数是否是循环节（应用性质3），并且因为性质1，它的约数是循环节，原串一定也是。 所以只要不断除以质因数（相当于从大到小枚举约数），缩小L的长度，最后就是最小的长度。 而一个重要的点在于，用上面方法来枚举约数是为了避免tle 在求它的质因数的时候，可以通过线性筛的过程求得，将时间法度由根号n 降为logn。 注意这里枚举到全长。 void pri() { for(int i = 2;i<= maxn;i++) { if(used[i] == 0) { sushu[++k] = i; nxt[i] = i;//质数就返回自己（方便多次乘方的查找）。 } for(int j = 1;j <= k && (long long)i*sushu[j]<= maxn;j++) { used[i*sushu[j]] = 1; nxt[i*sushu[j]] = sushu[j];（代表这个数是由这个质数将其表示为非质数，同时也是其质因数）。 if(i%sushu[j] == 0) { break; } } } } 这样通过nxt数组不断回跳，就可以找出所有质因数（多次乘方的也可以） 判定循环节的时候可以使用hash。 代码附上 #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define seed 13131 #define maxn 500005 using namespace std; typedef unsigned long long ull; char s[500005]; ull s1[500005]; ull ss[500005]; int sushu[500005]; int used[500005]; int nxt[500005]; int k; int ys[500005]; void pri() { for(int i = 2;i<= maxn;i++) { if(used[i] == 0) { sushu[++k] = i; nxt[i] = i; } for(int j = 1;j <= k && (long long)i*sushu[j]<= maxn;j++) { used[i*sushu[j]] = 1; nxt[i*sushu[j]] = sushu[j]; if(i%sushu[j] == 0) { break; } } } } int check(int l1,int r1,int l2,int r2) { if(s1[r1]-ss[r1-l1+1]*s1[l1-1] == s1[r2]-ss[r2-l2+1]*s1[l2-1]) { return 1; } return 0; } int main() { int n; scanf("%d", &n); scanf("%s",s+1); int q; scanf("%d", &q); for(int i = 1;i <= n;i++) { s1[i] = s1[i-1]*seed+s[i]-'a'+1; } ss[0] = 1; for(int i = 1;i <= n;i++) { ss[i] = ss[i-1]*seed; } pri(); for(int i = 1;i <= q;i++) { int l,r; scanf("%d%d", &l, &r); int len = r-l+1; int tt = 0; while(len != 1) { ys[++tt] = nxt[len]; len = len/nxt[len]; } len = r-l+1; for(int j = 1;j <= tt;j++) { int t = len/ys[j]; if(check(l,r-t,l+t,r) == 1) { len = t; } } printf("%d\n",len); } return 0; }