一段时间以前我曾经请求加过一个 hack 数据。

但这个数据貌似错掉了。我在本地构建了数据，能够输出正确答案。在 LOJ 是提交也得到 AC。我怀疑是 hack 数据出了问题。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
inline int read(){
    int x=0;int ch=getchar();
    while (!isdigit(ch)&&(ch!=EOF)) ch=getchar();
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x;
}
int n,f[500050],t,a,b,m,l,x,y,d,g,pr[100050],pc;
ll h[500050],p[500050],r=1e9+7;
char s[500050];
inline bool ch(int k){
	if(h[b]-h[a+k-1]==(h[b-k]-h[a-1])*p[k]) return true;
	return false;
}
int main(){
//	freopen("test1.in","r",stdin);
	n=read();
	for(int i=1;i<=n;i++){
		char c;
		while(1){
			c=getchar();
			if(c!=EOF) break;
		}
		s[i]=c;
	}
	t=read();
	for(int i=2;i<=n;i++){
		if(!f[i]) f[i]=i,pr[++pc]=i;
		for(int j=1;j<=pc;j++){
			if(i*pr[j]>n) break;
			if(!f[i*pr[j]]) f[i*pr[j]]=pr[j];
			if(i%pr[j]==0) break;
		}
	}
	p[0]=1;
	for(int i=1;i<=n;i++) p[i]=p[i-1]*r;
	for(int i=1;i<=n;i++) h[i]=h[i-1]+s[i]*p[i];
	while(t--){
		a=read(),b=read();
		m=b-a+1,l=m,d=m,g=m;
		while(m>1){
			x=f[m],y=0;
			while(f[m]==x){
				m/=f[m];
				y++;
			}
			d=g;
			for(int i=1;i<=y;i++){
				d/=x;
				if(ch(d)) l/=x;
				else break;
			}
		}
		printf("%d\n",l);
	}
	return 0;
}