摘要：
inlineintInt（）｛charc=getchar（）；intx=0；while（isdigit（c））x=（x<；3）+（x&llt；c=getchar（）；｝constantbase=19260817；=cnt；}intmain（）{n=Int（）；=n；fac[i]=fac[i-1]*base；++i）{l=Int（（）；r=Int（；len/=v[len]；r））len=u；
P3538 [POI2012]OKR-A Horrible Poem
hash+线性筛
题解 <----这篇写的不错（其实是我懒得码字了qwq）
判断一个长为 u 的子串是否为 长为 n 的主串的循环子串 只要比较 [1,n-u ]和 [u+1, n]的hash值即可（所以说我以前都是瞎搞〒▽〒）
想了想，还是加点注释吧，不然为啥要写博客总结呢（逃
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> using namespace std; typedef unsigned long long ull; inline int Int(){ char c=getchar(); int x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x; } const int base=19260817; int n,q,cnt,v[500002],prime[500002],it_pri[500002]; char a[500002]; ull h1[500002],fac[500002]; //自然溢出hash void get_prime(){ //线性筛筛素数 for(int i=2;i<=n;++i){ if(!v[i]) prime[++cnt]=v[i]=i; for(int j=1;j<=cnt;++j){ if(prime[j]>v[i]||prime[j]>n/i) break; v[prime[j]*i]=prime[j]; } } } inline bool check(int l1,int r1,int l2,int r2){ //hash值比较 ull p1=h1[r1]-h1[l1-1]*fac[r1-l1+1]; ull p2=h1[r2]-h1[l2-1]*fac[r2-l2+1]; return p1==p2; } int main(){ n=Int(); scanf("%s",a); fac[0]=1; for(int i=1;i<=n;++i){ h1[i]=h1[i-1]*base+(ull)a[i-1]; fac[i]=fac[i-1]*base; } //普通的hash get_prime(); q=Int(); int l,r; for(int i=1;i<=q;++i){ l=Int(); r=Int(); int t=0,len=r-l+1; while(len>1) it_pri[++t]=v[len],len/=v[len]; //分解质因数 len=r-l+1; for(int j=1;j<=t;++j){ int u=len/it_pri[j]; if(check(l,r-u,l+u,r)) len=u; //不断缩小循环子串的最小值 } printf("%d ",len); } return 0; }