题目大意

bzoj 2795

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

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

n<=500,000 , q<=2,000,000

分析

判循环节用hash

\(O(q\sqrt n)\)枚举因子？

TLE

注意一个特殊的性质

若长度len可为循环节，则若(klen) | n，(klen)也为循环节

不会出现两个循环节长度互质除非1是循环节

由于已知整个串是循环节

于是我们可以枚举质因子判断循环节能否缩短

线性筛预处理一波

\(O(q\log n)\)

原理

每个循环节都可以被最短循环节复制k倍表示

所以从原串缩短的过程中，能被最短循环节表示的本质没变，依然可以继续缩短

（反证假设不可以被最短循环节表示，则有它们的gcd才是最短循环节）

至于证明如果长度A是循环节，长度B是循环节，那么gcd(A,B)也是循环节

根据扩欧，存在 Ax+By=g

且根据循环节定义\(S[i]=S[i+k_1A+k_2B]\)

则对于\(\forall i\)都有\(S[i]=S[i+Ax+By]=S[i+gcd(A,B)]\)

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

typedef unsigned long long ull;

typedef long long LL;

const int M=500007;

const ull W=131;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n,m;

char s[M];

ull hsh[M],pw[M];

int prime[M],cnt;

int vis[M];

int split[M][20];

void init(){

	int i,j,k,t;

	vis[1]=1;

	for(i=2;i<M;i++){

		if(!vis[i]){

			prime[++cnt]=i;

			split[i][0]=1;

			split[i][1]=i;

		}

		for(j=1;j<=cnt;j++){

			if((LL)i*prime[j]>=M) break;

			t=i*prime[j];

			vis[t]=1;

			for(k=1;k<=split[i][0];k++) split[t][k]=split[i][k];

			split[t][0]=split[i][0];

			if(i%prime[j]==0) break;

			split[t][++split[t][0]]=prime[j];

		}

	}

}

ull gethsh(int x,int y){

	int len=y-x+1;

	return hsh[y]-hsh[x-1]*pw[len];

}

int main(){

	int i,j,x,y,len,z,tp,pri;

	n=rd();

	scanf("%s",s+1);

	m=rd();

	init();

	for(hsh[0]=0,i=1;i<=n;i++) hsh[i]=hsh[i-1]*W+s[i];

	for(pw[0]=1,i=1;i<=n;i++) pw[i]=pw[i-1]*W;

	while(m--){

		x=rd(),y=rd();

		len=y-x+1;

		z=len;

		for(j=1;j<=split[z][0];j++){

			pri=split[z][j];

			while(len%pri==0){

				tp=len/pri;

				if(gethsh(x,y-tp)!=gethsh(x+tp,y)) break;

				len/=pri;

			}

		}

		printf("%d\n",len);

	}

	return 0;

}