题意：给出一个由小写英文字母组成的字符串S，再给出q个询问，每个询问是[L,R]的区间形式，要求回答字符串S在该区间内(所构成的子串)的最短循环节.
分析：首先我们来谈谈循环节有哪些性质？因为简单易懂，就直接列出来了（只列举本题涉及到的）：
(1)一个字符串的循环节的长度一定是该字符串长度的约数.根据这条性质，我们可以知道如何枚举可能的循环节.
(2)若n是([l,r])的循环节，则一定满足([l,r-n])和([l+n,r])相同.根据这条性质，我们可以做到O(1)判断是否为循环节.
综上两条性质，我们的思路就比较清晰了.计算出该区间的长度之后(r-l+1),枚举它的每一个约数,并判断是不是循环节,从而得到最短循环节,上面说了判断可以做到O(1),所以现在需要考虑的是如何快速枚举约数,很容易想到的是线性筛素数法,因为在线性筛素数的过程中，我们可以得到区间长度的最小质因数，然后通过不断除以它的质因数,就相当于是在不断地从大到小枚举它的约数了.
再说一下，那个O(1)的判断可以借助字符串哈希值.
int n,m,tot;
int v[500005],prime[500005],divi[1005];
unsigned long long hash[500005],ha[500005];
char s[500005];
inline void getprime(){//线性筛素数(自学内容)
int num=0;//num记录素数个数
for(int i=2;i<=500005;i++){
if(!v[i]){
//v[i]==0,表示i是素数,因为从2开始枚举,v[2]肯定是0
//至于2后面的数，因为没有被筛出来,则代表是素数
//（如果i是被筛出来的数,v[i]就不为零了）
prime[++num]=i;//记录第num个素数
v[i]=i;//v[i]表示i的最小质因子
}
//借助已知素数,筛出合数：
for(int j=1;j<=num;j++){
if(prime[j]>v[i])break;
//如果i有比prime[j]更小的质因子,退出
if(prime[j]*i>n)break;
//如果i*prime[j]超出筛的范围,退出
v[prime[j]*i]=prime[j];
//合数prime[j]*i的最小质因子就是prime[j]
}
}
}
inline bool check(int l1,int r1,int l2,int r2){
if(hash[r1]-ha[r1-l1+1]*hash[l1-1]==
hash[r2]-ha[r2-l2+1]*hash[l2-1])return 1;
else return 0;
}//借助哈希值做到O(1)判断是否是循环节
int main(){
n=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++)
hash[i]=hash[i-1]*179+s[i]-'a'+1;
ha[0]=1;
for(int i=1;i<=n;i++)
ha[i]=ha[i-1]*179;
//哈希值,179只是个随缘质数,只要能降低冲突概率就行
//hash[]和ha[]都用的unsigned long long,让它自然溢出，一般情况下无碍
getprime();
m=read();
while(m--){
tot=0;//因为这里没有初始化，卡了一个小时..
int l=read(),r=read();
if(l==r){
puts("1");
continue;
}//可要可不要的特判优化
int len=r-l+1;//len区间长度
//区间长度不断不断除以它的质因数,将约数存入divi数组
//tot约数个数,divi[]数组里面约数保证了从大到小
while(len!=1){
divi[++tot]=v[len];
len=len/v[len];
}
len=r-l+1;
for(int i=1;i<=tot;i++){
int ans=len/divi[i];
if(check(l,r-ans,l+ans,r)){
len=ans;
}
}
//枚举可能的循环节,并判断是否合法
printf("%d
",len);
}
return 0;
}