【题解】A Horrible Poem

题目大意

给出一个由小写英文字母组成的字符串 S，再给出 q 个询问，要求回答 S 某个子串的最短循环节。

如果字符串 B 是字符串 A 的循环节，那么 A 可以由 B 重复若干次得到。

输入格式

第一行一个正整数 n，表示 S 的长度。

第二行 n 个小写英文字母，表示字符串 S 。

第三行一个正整数 q ，表示询问个数。

下面 q 行每行两个正整数 a,b，表示询问字符串 S[a..b] 的最短循环节长度。

输出格式

依次输出 q 行正整数，第 i 行的正整数对应第 i 个询问的答案。

输入样例

aaabcabc

1 3

3 8

4 8

输出样例

数据范围

1≤a≤b≤n≤5×10^5 , q≤2×10^5。

题解

容易想到，对于每一个子串，我们要枚举其循环节，而循环节的长度一定是子串长度的因子。所以关键是枚举出对于每一个数的所有因子。

对于每个子串，用$O(sqrt{n}) $的朴素枚举显然会TLE。所以我们要换一种枚举方法。

我们先欧拉筛求出$1... n$的所有质数，根据欧拉筛的枚举顺序，我们也可以顺便求出任意一个数$i$的最小质因子$mp[i]$。

枚举出这个有什么用呢？其实我们可以根据这个求出任意长度$len$的所有质因子。

我们用$t[i]$表示$len$的第$i$个质因子，我们不断记录$mp[len]$，然后让$len = frac{len}{mp[len]}$，直到$len = 1$为止。此时我们就可以得到$len$的$cnt$个质因子$t[1...cnt]$，且有$t[i] leqslant t[i + 1]$。

我们设最短循环节的长度为$len$。最开始我们然后$len$等于子串长度。

然后我们从$t[1]$开始枚举$t[i]$，我们先让$len = frac{len}{t[i]}$，然后判断此时的$len$是否是循环节长度，如果不是，则再让$len$乘回$t[i]$。判断完后继续枚举$t[i]$即可。这样我们就可以不断得到越来越小的循环节长度，直到得到答案。

#include <iostream>
#include <cstdio>
#include <cctype>

#define MAX_N (500000 + 5)

#define SIZE (1 << 21) 

#define Getchar() (pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, SIZE, stdin), pr1 == pr2) ? EOF : *pr1++) 
#define Putchar(ch) (pw < SIZE ? fw[pw++] = (ch) : (fwrite(fw, 1, SIZE, stdout), fw[(pw = 0)++] = (ch))) 

using namespace std;

char fr[SIZE], * pr1 = fr, * pr2 = fr;
char fw[SIZE];
int pw;

int Read() 
{
    int res = 0, sign = 1;
    char ch = Getchar();
    while(!isdigit(ch)) 
    {
        if(ch == '-') sign = -1;
        ch = Getchar();
    }
    while(isdigit(ch)) 
    {
        res = res * 10 + ch - '0';
        ch = Getchar();
    }
    return res * sign;
}

void Write(int val) 
{
    char a[15];
    int len = 0;
    if(val < 0) 
    {
        val = -val;
        Putchar('-');
    }
    do 
    {
        a[++len] = val % 10 + '0';
        val /= 10;
    }
    while(val);
    while(len) 
    {
        Putchar(a[len--]);
    }
    return;
}

typedef unsigned long long ull;
typedef const unsigned long long cull;
int n;
char s[MAX_N];
cull b = 29;
ull h[MAX_N], pb[MAX_N];
int p[MAX_N], mp[MAX_N], tot;

void Euler() 
{
    for(register int i = 2; i <= n; ++i) 
    {
        if(!mp[i]) p[++tot] = mp[i] = i;
        for(register int j = 1; i * p[j] <= n; ++j) 
        {
            mp[i * p[j]] = p[j];
            if(!(i % p[j])) break;
        }
    }
    return; 
}

void Hash()
{
    pb[0] = 1;
    for(register int i = 1; i <= n; ++i) 
    {
        h[i] = h[i - 1] * b + s[i] - 'a' + 1;
        pb[i] = pb[i - 1] * b;
    } 
    return;
}

ull Value(int lt, int rt) 
{
    return h[rt] - h[lt - 1] * pb[rt - lt + 1];
}

int main() 
{
    n = Read();
    for(register int i = 1; i <= n; ++i) 
    {
        s[i] = Getchar();
    }
    Euler();
    Hash();
    int q, lt, rt;
    q = Read();
    int t[MAX_N], cnt, len;
    while(q--) 
    {
        lt = Read();
        rt = Read();
        len = rt - lt + 1;
        cnt = 0;
        while(len > 1) 
        {
            t[++cnt] = mp[len];
            len /= mp[len];
        }
        len = rt - lt + 1;
        for(register int i = 1; i <= cnt; ++i)
        {
            len /= t[i];
            if(Value(lt, rt - len) != Value(lt + len, rt)) len *= t[i];
        }
        Write(len);
        Putchar('
');
    }
    fwrite(fw, 1, pw, stdout);
    return 0;
}

参考程序