[POI 19 Stage 2] A Horrible Poem

作法：

考慮枚舉所求子字串的長度$L$，我們知道$L$是給定子字串長度的因數，所以可以只枚舉其因數就可以了。確定$L$之後，假設詢問的區間為$[x,y]$，那麼判斷這個$L$是否可以的方法就只要看$[x,y-L]$和$[x+L,y]$這兩個字串是否一模一樣就可以了，證明並不難。而只要用 hash 就可以$O(1)$判斷了，因此就得到了一個$O(logn)$的解。但這樣傳上去 TLE 了，而只要再注意到：假設詢問的區間中有$x_1$個$a$，那麼分的塊數也一定要是$x_1$的因數，這樣就又縮減一些可能性了。因此我們變成枚舉切的塊數，所有的可能會是某個數的因數，直接用$O(\sqrt{n})$的找因數方法就可以了。

code :

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define LL long long
#define MOD 1000000009
using namespace std;
const int maxn=500000+10 ;
const int X=30007 ;
 
LL ha[maxn],pw[maxn] ;
inline LL gethash(int l,int r)
{
    return (ha[r]-ha[l]*pw[r-l]%MOD+MOD)%MOD ;
}
 
bool check(int l,int r,int num)
{
    if(num==1) return 1 ;
    int len=(r-l+1)/num ;
    return gethash(l,r-len)==gethash(l+len,r) ;
}
char s[maxn] ;
int sum[maxn][26] ;
main()
{
    int n ; scanf("%d%s",&n,s+1) ;
    int L=strlen(s+1) ;
    for(int i=0;i<=L;i++)
        pw[i]= i ? pw[i-1]*X%MOD : 1 ,
        ha[i]=(ha[i-1]*X+s[i]-'a')%MOD ;
    for(int j=1;j<=L;j++) for(int i=0;i<26;i++)
        sum[j][i]=sum[j-1][i]+(s[j]=='a'+i) ;
 
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        int l,r ; scanf("%d%d",&l,&r) ;
        int len=r-l+1 , g=len ,ans=0 ;
        for(int i=0;i<26;i++) g=__gcd(g,sum[r][i]-sum[l-1][i]) ;
        for(int i=1;i*i<=g;i++)
        {
            if(check(l,r,i)) ans=max(ans,i) ;
            if(check(l,r,g/i)) ans=max(ans,g/i) ;
        }
        printf("%d\n",len/ans) ;
    }
}