~~我也回一个40分的代码~~
```
#include<bits/stdc++.h>
using namespace std;
int vv[100000],cnt;
bool b[500050];
int n,l,r,m;
string s,a,qwq;
inline bool check(char a) {
for(register int i=l+1; i<=r; i++) {
if(a!=s[i])return false;
}
return true;
}
inline bool chenzhe(int i) {
for(register int j=l+i; j+i-1<=r; j+=i) {
qwq=s.substr(j,i);
if(qwq!=a)return false;
}
return true;
}
inline bool kkk(int u) {
for(register int i=2; i<=(u>>1); i++) {
if(!(u%i)) {
a=s.substr(l,i);
if(chenzhe(i)){
printf("%d\n",i);
return true;
}
}
}
return false;
}
int main() {
scanf("%d",&n);
for(register int i=2; i<=n; i++) {
if(!b[i]) {
vv[cnt++]=i;
}
for(register int j=0; j<cnt&&i*vv[j]<=n; j++) {
b[i*vv[j]]=1;
if(i%vv[j]==0)break;
}
}
cin>>s;
s='0'+s;
scanf("%d",&m);
while(m--) {
scanf("%d%d",&l,&r);
register int u=r-l+1;
if(u==1) {
printf("1\n");
continue;
}
if(!b[u]) {
a=s[l];
if(check(a[0]))printf("1\n");
else printf("%d\n",u);
} else {
if(!kkk(u))printf("%d\n",u);
}
}
return 0;
}
/*
15
acbacbbbcdbbcde
1
7 14
acb acb bbcd bbcd e
*/
```
by 风华正茂 @ 2018-10-09 18:22:55
@[风华正茂](/space/show?uid=113510) ~
by PPXppx @ 2018-10-09 18:53:23
@[Ym2011](/space/show?uid=112164) 咋了呀
by 风华正茂 @ 2018-10-09 19:04:42
60分代码+1
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int B=1000000007;
char s[500005];int l,a,b,ans[2000002];ULL p[500005],h[500005];
void getp()
{
p[0]=1;
for(int i=1;i<=500001;i++)p[i]=p[i-1]*B;
}
void hash1()
{
h[0]=0;
for(int i=1;i<=l;i++)h[i]=h[i-1]*B+s[i]-'a'+1;
}
int judge(int L)
{
ULL h1=h[L+a-1]-h[a-1]*p[L];
for(int i=2;i<=l/L;i++)
{
if(h1!=h[i*L+a-1]-h[i*L-L+a-1]*p[L])return 0;
}
return 1;
}
int main()
{
getp();
cin>>l;
scanf("%s",s+1);
hash1();
int T;cin>>T;
for(int Ti=1;Ti<=T;Ti++)
{
cin>>a>>b;l=b-a+1;
int f=1;
for(int i=1;i<=l/2;i++)
{
if(l%i==0)
{
if(judge(i))
{
f=0;
cout<<i<<endl;;
break;
}
}
}
if(f)cout<<l<<endl;
}
return 0;
}
```
by かみじょ @ 2018-12-11 11:38:46
### 60分代码＋１
```c
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
```
by 龙翔凤翥 @ 2019-01-27 18:03:20
### ６０分代码＋１
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define RN register int
int n,ans,flag,t=131;
unsigned int pow[1000101],has[1000101];
char str[1000101];
inline int read()
{
int k=1;int x=0;
char c=getchar();
while ((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')
k=-1,c=getchar();
while(c>='0'&&c<='9')
x=x*10+c-'0',c=getchar();
return k*x;
}
int main()
{
pow[0]=1;
for(RN i=1;i<=1000001;i++)
pow[i]=(pow[i-1]*t);
int xxx;
xxx=read();
scanf("%s",str+1);
int w=read();
for(RN i=1;i<=xxx;i++)
{
has[i]=(has[i-1]*t+(str[i]-'a'+1));
//cout<<has[i]<<" ";
}
//cout<<has[4]-has[2]*pow[2];
for(RN k=1;k<=w;k++)
{
flag=ans=1;
int x,y;
x=read(),y=read();
for(RN len=x;len<=y;len++)
if(!((y-x+1)%(len-x+1)))
{
flag=1;
unsigned int h=has[len]-has[x-1]*pow[len-x+1];
//cout<<"h= "<<h;
for(RN i=len;i<=y;i+=(len-x+1))
if(h!=has[i]-(has[i-len+x-1]*pow[len-x+1]))
{
flag=0;
break;
}
if(flag)
{ans=len-x+1;break;}
}
printf("%d\n",ans);
}
return 0;
}
```
by 龙翔凤翥 @ 2019-01-27 18:04:16
线性筛那里要开的大一点，我也不造为啥。。亲测能过。。
by kevin006 @ 2019-08-05 15:47:24