题解：

• 询问区间的整循环节
• 设区间长度为$n$
• 如果有循环节长为$x$和$y$，那由斐蜀定理得$gcd(x,y)$也一定为一个循环节；
• 假设最小的循环节长为$mn$，那么对于任何循环节长$x$，一定$mn | x$ , 否则$gcd(mn,x)<mn$矛盾
• 推出$\frac{n}{x} | \frac{n}{mn}$
• 所以每次提出$n$的一个质因子$p$，考虑是否可以分成$p$段，如果可以$n=\frac{n}{p}$继续找；
• 最后得出来的$n$就是最短的循环节；
• 分解质因子可以$O(n)$线筛最大/最小质因子，$O(logn)$分解；

•  #include<bits/stdc++.h>
  
   #define rg register
  
   #define il inline
  
   #define ull unsigned long long
  
   #define base 1234567891
  
   using namespace std;
  
   const int N=;
  
   int vis[N],pr[N],pt,v[N],n,m,len;
  
   ull pw[N],h[N];
  
   char gc(){
  
       static char*p1,*p2,s[];
  
       if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
  
       return(p1==p2)?EOF:*p1++;
  
   }
  
   int rd(){
  
       int x=;char c=gc();
  
       while(c<''||c>'')c=gc();
  
       while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();
  
       return x;
  
   }
  
   void pre(){
  
       for(rg int i=;i<=n;i++){
  
           if(!vis[i])pr[++pt]=i,v[i]=i;
  
           for(rg int j=,t;j<=pt&&pr[j]*i<=n;j++){
  
               vis[t=i*pr[j]]=;
  
               v[t]=pr[j];
  
               if(i%pr[j]==)break;
  
           }
  
       }
  
   }
  
   ull cal(int i,int j){return h[i+j-] - h[i-]*pw[j];}
  
   int main(){
  
       #ifndef ONLINE_JUDGE
  
       freopen("bzoj2795.in","r",stdin);
  
       freopen("bzoj2795.out","w",stdout);
  
       #endif
  
       n=rd(); pre();
  
       char ch=gc();while(!isalpha(ch))ch=gc();
  
       for(rg int i=pw[]=;i<=n;i++,ch=gc()){
  
           h[i]=h[i-]*base+ch;
  
           pw[i]=pw[i-]*base;
  
       }
  
       m=rd();
  
       for(rg int i=,l,r;i<=m;i++){
  
           l=rd(); r=rd();
  
           int ans=r-l+,now=ans,t;
  
           while(now>){
  
               t=ans/v[now];
  
               if(cal(l,ans-t)==cal(l+t,ans-t))ans/=v[now];
  
               now/=v[now];
  
           }
  
           printf("%d\n",ans);
  
       }
  
       return ;
  
   }

  bzoj2795