A Horrible Poem题解

$O(q\sqrt{n})$ 做法的话，可以枚举到 $\sqrt{n}$ ，另外一半除出来存到数组里面，如果跑完没找到循环节的话那么最近存进数组里面的就是答案了。但是这样基本要跑满，所以会T。 $n\log n$ 做法的话，可以根据算数基本定理把len分解了，那么对每个质因子，如果len/p是循环节的话，就将len/p，这样子能做到 $q\log n$ 。至于判断是否循环节，如果一个字符串如果有循环节长度为x，则 $hash(l+x,r)=hash(l,r−x)$

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 2000100
#define ll unsigned long long
#define base 233

ll h[N], p[N];
char s[N];
int n, f[N], lp[N], pr[N], cnt;
bool vis[N];

ll get_hash(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }

bool check(int x, int l, int r) {
    return get_hash(l, r - x) == get_hash(l + x, r);
}

void pre_test() {
    p[0] = 1;
    for(int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] * base;
        h[i] = h[i - 1] * base + (ll)s[i];
    }
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) pr[++cnt] = i, lp[i] = i;
        for(int j = 1; j <= cnt && i * pr[j] <= n; ++j) {
            vis[i * pr[j]] = 1;
            lp[i * pr[j]] = pr[j];
            if(i % pr[j] == 0) break;
        }
    }
}

int main() {
    scanf("%d%s", &n, s + 1);
    pre_test();
    int m, l, r; scanf("%d", &m);
    while(m--) {
        scanf("%d%d", &l, &r);
        int now = r - l + 1, v = r - l + 1;
        while(v != 1) {
            if(check(now / lp[v], l, r)) now /= lp[v];
            v /= lp[v];
        }
        printf("%d\n", now);
    }
    return 0;
}