Description：

给出一个由小写英文字母组成的字符串 $S$ ，再给出 $q$ 个询问，要求回答 $S$ 某个子串的最短循环节。

$1\leqslant |S|\leqslant5\times 10^5,1\leqslant q\leqslant 2\times 10^6$

Solution：

先线性筛出每个数的最小质因数，然后把整个字符串 $hash$ 起来，然后对于每个询问，把他标准分解，这个复杂度是 $O(\log n)$ 的，然后枚举所有约数，看 $lenth$ 除掉这个数后是否还是原串的一个循环节，如果是就除掉，最后剩下的就是答案，关于如何判断 $len$ 是否是 $l\sim r$ 的循环节，只要判断 $l\sim r-len$ 和 $l+len\sim r$ 相等就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 500010

char c[MAXN];

#define BASE1 19260817

#define BASE2 233333

#define MOD1 1000000007

#define MOD2 998244353

#define fi first

#define se second

struct HASH_map

{

	int h1[MAXN],h2[MAXN];

	int power1[MAXN],power2[MAXN];

	void build()

	{

		power1[0] = power2[0] = 1;

		for(int i = 1;i <= n;++i)

		{

			power1[i] = (1ll * power1[i - 1] * BASE1) % MOD1;

			h1[i] = (1ll * h1[i - 1] * BASE1 + c[i]) % MOD1;

			power2[i] = (1ll * power2[i - 1] * BASE2) % MOD2;

			h2[i] = (1ll * h2[i - 1] * BASE2 + c[i]) % MOD2;

		}

		return;

	}

	pair<int,int> get(int l,int r)

	{

		pair<int,int> res;

		res.fi = (h1[r] - 1ll * h1[l - 1] * power1[r - l + 1] % MOD1 + MOD1) % MOD1;

		res.se = (h2[r] - 1ll * h2[l - 1] * power2[r - l + 1] % MOD2 + MOD2) % MOD2;

		return res;

	}

}h;

bool isprime[MAXN];

int prime[MAXN],tot = 0,mindiv[MAXN];

void sieve()

{

	for(int i = 2;i <= n;++i)isprime[i] = true;

	for(int i = 2;i <= n;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			mindiv[i] = i;

		}

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			mindiv[i * prime[j]] = prime[j];

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

int s[MAXN],top;

bool check(int l,int r,int len)

{

	return h.get(l,r - len) == h.get(l + len,r);

}

int main()

{

	scanf("%d",&n);

	sieve();

	scanf("%s",c + 1);

	h.build();

	scanf("%d",&m);

	int l,r;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&l,&r);

		int len = r - l + 1;

		top = 0;

		while(len != 1)

		{

			s[++top] = mindiv[len];

			len /= mindiv[len];

		}

		len = r - l + 1;

		for(int k = 1;k <= top;++k)

		{

			if(check(l,r,len / s[k]))len /= s[k];

		}

		printf("%d\n",len);

	}

	return 0;

}