【BZOJ】2795: [Poi2012]A Horrible Poem

题意

一个长度为\(n(n \le 500000)\)的字符串\(s\)，给\(q(q \le 2000000)\)个询问，每个询问给一个区间\([l, r]\)，求这个区间内最短的循环节。

分析

分析以下可以知道：

1. 假设循环节长度为\(len\)，则\(s[l, r-len]=s[l+len, r]\)。
2. \(len|(r-l+1)\)
3. 如果\(len\)是循环节，则\(len * p\)也是循环节\((len * p|(r-l+1))\)

题解

首先判两个串是否相等用hash即可。
根据\(1, 2\)我们很容易得到\(O(qn^{0.5})\)的做法。
可是由于性质\(3\)的存在，我们先分解\((r-l+1)\)的质因数，然后依次考虑删去质因数即可。
复杂度\(O(qlogn)\)

#include <bits/stdc++.h>
using namespace std;
inline int getint() {
    int x=0, c=getchar();
    for(; c<48||c>57; c=getchar());
    for(; c>47&&c<58; x=x*10+c-48, c=getchar());
    return x;
}
const unsigned int N=500005, mo=1e9+7;
int p[N], cnt, m[N], bg[N];
unsigned int a[N], po[N];
void init(int n) {
    for(int i=2; i<=n; ++i) {
        if(!bg[i]) {
            bg[i]=i;
            p[cnt++]=i;
        }
        for(int j=0, t; j<cnt; ++j) {
            t=p[j]*i;
            if(t>n) {
                break;
            }
            bg[t]=p[j];
            if(i%p[j]==0) {
                break;
            }
        }
    }
}
inline bool check(int a, int b, int c, int d) {
    return m[b]-m[a-1]*po[b-a+1]==m[d]-m[c-1]*po[d-c+1];
}
int main() {
    int n=getint();
    init(n);
    po[0]=1;
    for(int i=1; i<=n; ++i) {
        m[i]=m[i-1]*mo+getchar();
        po[i]=po[i-1]*mo;
    }
    int q=getint();
    for(; q--; ) {
        int l=getint(), r=getint(), len=r-l+1;
        for(int x=len; x>1; ) {
            int y=bg[x];
            for(; len%y==0 && check(l, r-len/y, l+len/y, r); len/=y);
            for(; x%y==0; x/=y);
        }
        printf("%d\n", len);
    }
    return 0;
}