题意

一个长度为\(n(n \le 500000)\)的字符串\(s\)，给\(q(q \le 2000000)\)个询问，每个询问给一个区间\([l, r]\)，求这个区间内最短的循环节。

分析

分析以下可以知道：

1. 假设循环节长度为\(len\)，则\(s[l, r-len]=s[l+len, r]\)。
2. \(len|(r-l+1)\)
3. 如果\(len\)是循环节，则\(len * p\)也是循环节\((len * p|(r-l+1))\)

题解

首先判两个串是否相等用hash即可。

根据\(1, 2\)我们很容易得到\(O(qn^{0.5})\)的做法。

可是由于性质\(3\)的存在，我们先分解\((r-l+1)\)的质因数，然后依次考虑删去质因数即可。

复杂度\(O(qlogn)\)

#include <bits/stdc++.h>

using namespace std;

inline int getint() {

	int x=0, c=getchar();

	for(; c<48||c>57; c=getchar());

	for(; c>47&&c<58; x=x*10+c-48, c=getchar());

	return x;

}

const unsigned int N=500005, mo=1e9+7;

int p[N], cnt, m[N], bg[N];

unsigned int a[N], po[N];

void init(int n) {

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

		if(!bg[i]) {

			bg[i]=i;

			p[cnt++]=i;

		}

		for(int j=0, t; j<cnt; ++j) {

			t=p[j]*i;

			if(t>n) {

				break;

			}

			bg[t]=p[j];

			if(i%p[j]==0) {

				break;

			}

		}

	}

}

inline bool check(int a, int b, int c, int d) {

	return m[b]-m[a-1]*po[b-a+1]==m[d]-m[c-1]*po[d-c+1];

}

int main() {

	int n=getint();

	init(n);

	po[0]=1;

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

		m[i]=m[i-1]*mo+getchar();

		po[i]=po[i-1]*mo;

	}

	int q=getint();

	for(; q--; ) {

		int l=getint(), r=getint(), len=r-l+1;

		for(int x=len; x>1; ) {

			int y=bg[x];

			for(; len%y==0 && check(l, r-len/y, l+len/y, r); len/=y);

			for(; x%y==0; x/=y);

		}

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

	}

	return 0;

}