P3538 [POI2012]OKR-A Horrible Poem

给定一个串和多个区间，要求出区间最短循环节长度

1.判断一个字符串是该区间的循环节，可以O（1）hash判定，设枚举的循环节长度为t，判断[l,r-t]与[l+t,r]相等否即可
2.长度x是区间的一个循环节，y是x的倍数且是区间长度的约数，那么y也是循环节
3.对于多组询问的分解质因数，我们不需要全部预处理出来，也不需要每次都用试除法去试，我们可以用求出每个数的最小质因子设为v[x]，然后用x=x/v[x]，这些v[x]就是原数x的质因子集合，比试除法快很多

typedef unsigned long long ull;
const int N = 5e5 + 79;
const ull base = 13131;
int n, x, y, q;
ull p[N], H[N];
char s;
inline bool check(int l, int r, int x, int y) {
	return H[r] - H[l - 1] * p[r - l + 1] == H[y] - H[x - 1] * p[y - x + 1];
}


int v[N],prime[N],t;
inline void EulerSieve(int mx){
	rep(i,2,mx){
		if(!v[i]){
			v[i]=i;
			prime[++t]=i;
		}
		rep(j,1,t){
			if(1ll*prime[j]*i>mx||prime[j]>i) break;
			v[i*prime[j]]=prime[j];
		}
	}
}

int a[N];
inline void solve(int x, int y) {
	int len = y - x + 1;
	int cnt=0;
	while(len != 1) {
		a[++cnt] =v[len];
		len/=v[len];
	}
	len=y-x+1;
	rep(i,1,cnt){
		int t=len/a[i];//μ￥???-?·?ú3¤?è 
		if(check(x,y-t,x+t,y) ){
			len/=a[i];
		}
	}
	out(len,'\n');
}

int main() {
	read(n);
	p[0] = 1;
	rep(i, 1, n) {
		while((s = gt()) < 'a' || s > 'z');
		p[i] = p[i - 1] * base;
		H[i] = H[i - 1] * base + s;
	}
	EulerSieve(n);
	read(q);
	while(q--) {
		read(x);
		read(y);
		solve(x, y);
	}
	return 0;
}