题意

给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。

正整数n (n<=500,000)，表示S的长度。
正整数q (q<=2,000,000)，表示询问个数。

分析

参照ww140142的题解。

首先这问题画一画发现它绝对不是什么数据结构能维护的，因为这东西毫无可并性；

所以如果考虑暴力一些呢？

发现循环节长度一定是区间长度n的约数，可以枚举n的约数；

验证利用RKhash的特性，可以O(1)取出一段hash值；

比较[l,r]区间len是否为循环节，和比较[l+len-1,r]和[l,r-len+1]这两段的hash值是等价的；

时间复杂度为O(q√n)，看起来。。并不能过！

继续优化，现在算法的瓶颈是枚举约数的部分；

那么我们利用质因数分解，将n分解为多个质因子的乘积；

如果进行一步线性筛的预处理，这一步可以做到log级！

具体就是将vis[i*pri[j]]=1这一步中再记录一个i*pri[j]的最小质因子为pri[j]，然后分解时每次除这东西；

分解降到了log级，但是对一一枚举约数没什么作用；

这里又有一个性质，如果存在一个长度为len的循环节，那么对于满足klen|n的klen，都是循环节；

这个还是比较显然的，然后就可以倒着搞，每次用n除一个质因子，然后判断判断，复杂度\(O(n \log n)\)就可以过了；

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read()
{
    rg T data=0;
    rg int w=1;
    rg char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        data=data*10+ch-'0';
        ch=getchar();
    }
    return data*w;
}
template<class T>il T read(rg T&x)
{
    return x=read<T>();
}
typedef unsigned long long ll;

co int seed=131,N=5e5+1;
char str[N];
ll hash[N],Pow[N];
int pri[N],fp[N],st[N],top,cnt;

bool judge(int l,int r,int len)
{
    return hash[r-len]-hash[l-1]*Pow[r-len-l+1]==hash[r]-hash[l+len-1]*Pow[r-l-len+1];
}

void init(int n)
{
    Pow[0]=1;
    for(int i=1;i<=n;++i)
    {
        hash[i]=hash[i-1]*seed+str[i];
        Pow[i]=Pow[i-1]*seed;
    }
    for(int i=2;i<=n;++i)
    {
        if(!pri[i])
            pri[++cnt]=i,fp[i]=i;
        for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
        {
            pri[i*pri[j]]=1;
            fp[i*pri[j]]=pri[j];
            if(i%pri[j]==0)
                break;
        }
    }
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int n,m;
    read(n),scanf("%s",str+1),read(m);
    init(n);
    for(int k=1;k<=m;++k)
    {
        int l,r,len;
        read(l),read(r);
        len=r-l+1;
        top=0;
        while(len!=1)
        {
            st[++top]=fp[len];
            len/=fp[len];
        }
        len=r-l+1;
        for(int i=1;i<=top;++i)
            if(judge(l,r,len/st[i]))
                len/=st[i];
        printf("%d\n",len);
    }
    return 0;
}

BZOJ2795 [Poi2012]A Horrible Poem

原文：https://www.cnblogs.com/autoint/p/10326821.html