题目链接

BZOJ2795

BZOJ2890

BZOJ3647

题解

三倍经验！

我们要快速求区间最小循环节

我们知道循环节有如下性质：

①当\(L\)为循环节长度，那么\(s[l...r - L] = s[l + L...r]\)且\(L | (r - l + 1)\)

②如果\(L\)为循环节，那么\(L x\)也为循环节

一个比较暴力的思想是枚举\(len = r - l + 1\)的因子，用\(hash\)去判是否相同，这样做是\(O(q\sqrt{n})\)的，过于暴力

由性质②我们知道，最后的答案\(L\)一定是\(len\)删除若干个质因子的结果，所以我们只需枚举质因子即可

由于质因子个数是\(O(logn)\)的，所以预处理一下即可\(O(logn)\)，枚举质因子

复杂度\(O(qlogn)\)

要注意，\(P3647\)卡自然溢出

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

#define ULL unsigned long long int

using namespace std;

const int maxn = 500005,maxm = 100005,INF = 1000000000,P = 2001611;

inline int read(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

ULL pw[maxn],h[maxn];

LL pw2[maxn],h2[maxn];

char s[maxn];

int n,q,fac[maxn],p[maxn],pi,isn[maxn];

void init(){

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

		if (!isn[i]) p[++pi] = i,fac[i] = i;

		for (int j = 1; j <= pi && i * p[j] <= n; j++){

			isn[i * p[j]] = true; fac[i * p[j]] = p[j];

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

		}

	}

}

inline bool check(int l,int r,int ll,int rr){

	return h[r] - h[l - 1] * pw[r - l + 1] == h[rr] - h[ll - 1] * pw[rr - ll + 1]

		&& ((h2[r] - h2[l - 1] * pw2[r - l + 1] % P) % P + P) % P == ((h2[rr] - h2[ll - 1] * pw2[rr - ll + 1] % P) % P + P) % P;

}

int main(){

	n = read();

	pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 107;

	pw2[0] = 1; for (int i = 1; i <= n; i++) pw2[i] = pw2[i - 1] * 107 % P;

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

	init();

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

		h[i] = h[i - 1] * 107 + s[i];

		h2[i] = (h2[i - 1] * 107 % P + s[i]) % P;

	}

	q = read();

	int l,r,len,ans;

	while (q--){

		l = read(); r = read(); len = r - l + 1;

		ans = len;

		for (int x = len; x > 1; x /= fac[x]){

			int L = ans / fac[x];

			if (check(l,r - L,l + L,r))

				ans = L;

		}

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

	}

	return 0;

}