BZOJ2795:[Poi2012]A Horrible Poem 暴力+hash(&&BZOJ2890)

思路:

一开始的暴力非常容易:对于每一组询问直接暴力枚举答案即可.易知答案仅可能是字串长度的约数,再利用hash\(O(1)\)判断.因此单组询问的复杂度\(O(\sqrt{n})\).这种方法比较卡常数.

其实,存在一种更加科学的方法.

我们将长度分解质因数,考虑每个质因子的幂次.这样即可在\(O(logn)\)的时间内出解.十分科学.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF 0x3f3f3f3f
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    char buf[20000000],*o=buf;
    template<typename T>inline void Print(T x){
        static int stk[100];
        if(x<0)x=-x,*o++='-';
        if(!x)*o++=48;else{int top=0;for(;x;x/=10)stk[++top]=x%10;for(int i=top;i;--i)*o++=48+stk[i];}
        *o++='\n';
    }
    inline void Final(){fwrite(buf,1,o-buf,stdout);}
}
 
#define N 500010
 
typedef long long LL;
static const int seed=131;
static const int mod=(1e9)+9;
 
int n,f[N],mi[N];char s[N];
 
inline int get(int l,int r){
    return (f[l]-(LL)f[r+1]*mi[r-l+1]%mod+mod)%mod;
}
inline bool same(int l1,int r1,int l2,int r2){
    return get(l1,r1)==get(l2,r2);
}
 
int p[N],minp[N],cnt;bool np[N];
inline void pre(int n){
    register int i,j;
    for(i=2;i<=n;++i){
        if(!np[i])p[++cnt]=minp[i]=i;
        for(j=1;j<=cnt&&p[j]*i<=n;++j){
            np[i*p[j]]=1,minp[i*p[j]]=min(minp[i],p[j]);
            if(i%p[j]==0)break;
        }
    }
}
 
inline int Solve(int l,int r){
    int len=r-l+1;if(len==1)return 1;
    int tmp=len,res=len;
    while(tmp!=1){
        int nowp=minp[tmp],ans=1,calclen=len,t=1;
        while(1){
            if(calclen==len||same(l,l+(len-calclen)-1,r-(len-calclen)+1,r))ans=max(ans,t);
            if(calclen%nowp!=0)break;
            t*=nowp,calclen/=nowp;
        }
        for(res/=ans;tmp%nowp==0;tmp/=nowp);
    }
    return res;
}
int main(){
    using namespace Fio;
    scanf("%d",&n);scanf("%s",s+1);
    register int i;
    for(i=n;i>=1;--i)f[i]=((LL)seed*f[i+1]+s[i]-'a')%mod;
    for(mi[0]=1,i=1;i<=n;++i)mi[i]=(LL)mi[i-1]*seed%mod;
    pre(n);
     
    int m;Get(m);int l,r;
    while(m--){
        Get(l),Get(r);
        Print(Solve(l,r));
    }
    Final();
    return 0;
}