BZOJ2795 [Poi2012]A Horrible Poem

题面在这里

​

其实挺简单的……

考虑\(S[1..x]\)是S的循环节，当且仅当\(S[1..n-x]=S[1+x,n]\)

这个可以用哈希快速判断

因为循环节一定是最小循环节的倍数，而n一定是S的循环节

那么就可以从n开始，枚举并排除质因子，从而得到最小质因子

这个用线性筛预处理最小质因子\(O(logn)\)枚举就好了

​

示例程序：

#include<cstdio>
#define ull unsigned long long

const int maxn=500005;
int n,q,p[maxn],nxt[maxn]; bool vis[maxn];
char s[maxn];
void makep(int n){
	nxt[1]=1;
	for (int i=2;i<=n;i++){
		if (!vis[i]) p[++p[0]]=i,nxt[i]=i;
		for (int j=1;j<=p[0]&&i*p[j]<=n;j++){
			vis[i*p[j]]=1;nxt[i*p[j]]=p[j];
			if (i%p[j]==0) break;
		}
	}
}
ull sum[maxn],pw[maxn];
inline ull getha(int l,int r){
	if (l>r) return 0;
	return sum[r]-sum[l-1]*pw[r-l+1];
}
int main(){
	scanf("%d%s",&n,s+1);makep(n);pw[0]=1;
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]*233+s[i],pw[i]=pw[i-1]*233;
	scanf("%d",&q);
	while (q--){
		int l,r,tem,len,mn;scanf("%d%d",&l,&r);
		for (tem=len=r-l+1,mn=nxt[tem];tem>1;mn=nxt[tem]){
			while (len%mn==0&&getha(l,r-len/mn)==getha(l+len/mn,r)) len/=mn;
			while (tem%mn==0) tem/=mn;
		}
		printf("%d\n",len);
	}
	return 0;
}