[POI2012]OKR-A Horrible Poem

 1 #include<bits/stdc++.h>
 2 #define ull unsigned long long
 3 using namespace std;
 4 inline int read(){
 5     int ans=0,f=1;char chr=getchar();
 6     while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
 7     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 8     return ans*f;
 9 }
10 const int M=5e5+5;
11 const int B=131;
12 int n,q,l,r,len,x;
13 bool ff[M];
14 vector<int> g[M];
15 ull t[M],h[M];
16 char s[M];
17 inline ull Get(int l,int r){return h[r]-h[l-1]*t[r-l+1];}
18 inline void Hash(int i=0){
19     for(i=1,t[0]=1;i<=n;i++) t[i]=t[i-1]*B;
20     for(i=1;i<=n;i++) h[i]=s[i]+h[i-1]*B;
21 }
22 inline void Pre(){
23     for(int i=2;i<=n;i++)    if(!ff[i])for(int j=i;j<=n;j+=i)ff[j]=1,g[j].push_back(i);
24     for(int i=1;i<=n;i++)    sort(g[i].begin(),g[i].end());
25 }
26 int main(){
27     n=read();
28     scanf("%s",s+1);
29     q=read();Hash();Pre();
30     while(q--){
31         l=read(),r=read();len=x=r-l+1;
32         for(int i=0,ll=g[len].size();i<ll;i++){
33             int p=g[len][i];
34             while(x%p==0 && Get(l,r-x/p)==Get(l+x/p,r)) x/=p;
35         }printf("%d\n",x);
36     }
37     return 0;
38 }