循环节的经典性质
n是[l,r]这一段的循环节的充要条件是[l,r-n]和[l+n,r]相同 且n是长度的约数
然后不难想到根号的穷举约数的做法
有没有更好的做法，我们知道如果n是一个循环节，那么k*n也必定是一个循环节
我们只要穷举质因子，不断除以原长并保证其仍是循环节，直到不能再小为止即可
穷举质因子我们可以记录每个数的最小质因数（显然可以用线性筛搞），然后不断消去即可
这样就变成了nlogn的复杂度
注意这道题最好写双hash，由于pascal不能自然溢出，我卡出一个可以过的单hash……
const mo=;
bas=; var p,v,d,h:array[..] of longint;
len,l,r,m,j,k,i,n,t:longint;
s:ansistring; function hash(x,y:longint):longint;
begin
exit((h[x]-int64(h[y+])*int64(d[y-x+]) mod mo+mo) mod mo);
end; begin
readln(n);
for i:= to n do
begin
if v[i]= then
begin
v[i]:=i;
inc(t);
p[t]:=i;
end;
for j:= to t do
begin
if i*p[j]>n then break;
v[i*p[j]]:=p[j];
if i mod p[j]= then break;
end;
end;
d[]:=;
for i:= to n do
d[i]:=d[i-]*bas mod mo;
readln(s);
for i:=n downto do
h[i]:=(h[i+]*bas+ord(s[i])) mod mo;
readln(m);
for i:= to m do
begin
readln(l,r);
len:=(r-l+);
k:=len;
while k> do
begin
j:=v[k];
while (len mod j=) and (hash(l,r-len div j)=hash(l+len div j,r)) do len:=len div j;
while k mod j= do k:=k div j;
end;
writeln(len);
end;
end.