A Horrible Poem-字符串哈希+线性筛

A Horrible Poem-字符串哈希+线性筛

题目描述

题解

首先明确几个性质
1，循环节的长度必为该区间$S[a...b]$长度的约数—显而易见
2，当$S[a...b-len]==S[a+len...b]$时，$S[x...y]$必为$S[a...b]$的循环节；($len$为$S[x...y]$的长度)
证明可以自己手玩，这是我们判断循环节的重要根据
根据这2条性质，算法显而易见，枚举$l$的约数($l$为$S[a...b]$的长度),然后哈希判断是否为循环节，但该题卡$O(n\surd n)$,因此线性筛横空而出，首先预处理-线性筛，维护出每个数的最小质因数，然后比如找$l$的质因数时就递归思想，继续找$l/v[l]$的质因数，($v[i]$表示$i$的最小质因数)

代码

#include<bits/stdc++.h>//字符串哈希判循环节 
#define M 500009
#define LL unsigned long long
using namespace std;
int n,q,v[M],p[M],t[M],cnt;
LL has[M],mi[M];
char s[M];
const int h=31;
int read(){int f=1,re=0;char ch;for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());if(ch=='-'){ch=getchar();f=-1;}for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';return re*f;
}
void init(){for(int i=2;i<=n;i++){if(!v[i]){v[i]=i;p[++cnt]=i;}for(int j=1;j<=cnt;j++){if(p[j]*i>n||v[i]<p[j]) break;v[p[j]*i]=p[j];}}cnt=0;
}
LL gethas(int l,int r){return has[r]-has[l-1]*mi[r-l+1];
}
int main(){n=read(),init();scanf("%s",s+1),mi[0]=1;for(int i=1;i<=n;i++){has[i]=has[i-1]*h+(s[i]-'a');mi[i]=mi[i-1]*h;}q=read();for(int i=1;i<=q;i++){int l=read(),r=read();int len=r-l+1;cnt=0;while(len!=1){t[++cnt]=v[len];len=len/v[len];//依次找len的质因数 }len=r-l+1; for(int j=1;j<=cnt;j++){//逐渐缩小长度 int ans=len/t[j];if(gethas(l,r-ans)==gethas(l+ans,r)) len=ans;}printf("%d\n",len);}return 0;
}