难度： 蓝

算法： 字符串哈希，质数，素数判断，筛法

A Horrible Problem.

给定一个字符串，$m$ 次询问，每次询问一个子串，求其最小循环节。

记这个字符串为 $s$，第 $i$ 个字符为 $s_i$，以 $a$ 开头 $b$ 结尾的子串记为 $s_{a,b}$。令当前处理的字串为 $s_{a,b}$，记 $m=a+b-1$。

不难得到，如果 $c$ 不等于 $m$，则 $c$ 为 $s_{a,b}$ 的循环节的充分必要条件是 $s_{a,b-c}=s_{a+c,b}$。这个判断可以使用字符串哈希在 $O(1)$ 的时间内完成。

如果 $c$ 为 $s_{(a,b)}$ 的循环节，那么对于任意满足 $c|k,k|m$ 的 $k$，$k$ 仍为 $s_{a,b}$ 的循环节。

那么记当前最优答案为 $c$。将 $m$ 因式分解得到 $m=p_1^{r_2}p_2^{r_2}...p_x^{r_x}$，由于上面的性质有 $c|k$，那么令 $c=p_1^{t_1}p_2^{t_2}...p_x^{t_x}$。现在的问题就是求出每一个 $t$。假设我们现在正在处理 $t_1$。假设 $t_1=q$，那么有 $\frac{m}{p_1^{t_1-q}}$ 为 $s_{(a,b)}$ 的循环节， $\frac{m}{p_1^{t_1-q+1}}$ 不为 $s_{(a,b)}$ 的循环节。这里没有二分的必要，可以直接暴力判断。依次求出每个 $t$，最后通过 $c=p_1^{t_1}p_2^{t_2}...p_x^{t_x}$ 算出 $c$ 即可。

对于质因数分解，可以用筛子预处理每个数的最小质因子。每次质因数分解可在 $\log(m)$ 时间内完成。

但是这题卡的很死，所以要卡一下常：

1.对所有主函数以外的函数使用 inline。

2.int 的计算应该比 ll 或者 ull 快。能用 int 的用 int。

3.读入量太大了，使用快读。

#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(){
	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;
}