【题意】
给定一个字符串,q次询问l-r的最短循环节
【分析】z
显然,循环节是len的因子,所以我们可以通过枚举因子的方式来判断
这里,我们筛素数的同时,记录i的最小质因子min_fac[i],然后继续把i作为一个因数后,继续分解i/min_fac[i]
然后这里判断长度为j的是不是循环节的时候,注意循环节的充要条件就是[l,r-j]=[l+j,r],用哈希即可O(1)判断
【代码】
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=5e5+5; int vis[maxn],min_fac[maxn],fac[maxn],prime[maxn]; int cnt,tot; const int base=1313131; const int mod=1e9+7; char s[maxn]; ll pw[maxn],has[maxn]; int n,q; ll Hash(int l,int r) { return ((has[r]-has[l-1]*pw[r-l+1]%mod)%mod+mod)%mod; } bool judge(int l,int r,int len) { return Hash(l,r-len)==Hash(l+len,r); } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); for(int i=2;i<maxn;i++) { if(!vis[i]) { prime[++cnt]=i; min_fac[i]=i; } for(int j=1;j<=cnt && prime[j]*i<maxn;j++) { vis[i*prime[j]]=1; min_fac[i*prime[j]]=prime[j]; if(i%prime[j]==0) break; } } pw[0]=1; scanf("%d",&n); scanf("%s",s+1); for(int i=1;i<=n;i++) pw[i]=pw[i-1]*base%mod; for(int i=1;i<=n;i++) has[i]=(has[i-1]*base+s[i]-'a'+1)%mod; int l,r; scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%d%d",&l,&r); int len=r-l+1; if(judge(l,r,1)) printf("1\n"); else { tot=0; while(len!=1) { fac[++tot]=min_fac[len]; len/=min_fac[len]; } len=r-l+1; for(int j=1;j<=tot;j++) if(judge(l,r,len/fac[j])) len/=fac[j]; printf("%d\n",len); } } return 0; }