原題鏈接

解析

如果你還不會利用哈希 \(O(n)\) 找循環節，那么你應該先去做 P4391。

由于我們要求的是完整周期，所以循環節長度必定為所選片段長度的因子，于是可以很輕松地得到一個 \(O(q \sqrt n)\) 的做法。

設查詢的字符串為 \(a\)。觀察到若字符串 \(b\) 是一個完整周期，則對于所有滿足 \(k \cdot \operatorname{len}(b) \mid \operatorname{len}(a)\) 的 \(k\)，\(b^k\) 也是一個完整周期。

設 \(c\) 為最短完整周期且 \(c^x=a\)，很多題解到這里就直接開始對 \(x\) 分解質因數了，具體地，維護一個當前答案 \(ans\)，初始為 \(\operatorname{len}(a)\)，對于 \(\operatorname{len}(a)\) 的每個質因子 \(d\)，判斷 \(c[1,\dfrac{ans}w0obha2h00]\) 是否是一個完整周期，如果是，則令 \(ans \gets \dfrac{ans}w0obha2h00\)。

但實際上還需要說明除的時候不會把 \(\operatorname{len}(c)\) 的質因子除掉。事實上，不存在一個字符串 \(d\) 使得 \(d\) 是 \(a\) 的完整周期且 \(c\) 不是 \(d\) 的完整周期。使用周期引理可以輕松地證明這個命題。

周期引理：若 \(p,q\) 是字符串 \(S\) 的兩個周期且 \(p + q \le \operatorname{len}(S) +\gcd(p,q)\)，則 \(\gcd(p,q)\) 也是 \(S\) 的一個周期。

所以如果存在這樣的 \(d\) 則必定存在一個長度為 \(\gcd(\operatorname{len}(c),\operatorname{len}(d))\) 的完整周期，原命題得證。

在線性篩素數的同時處理出每個數的最小質因子，我們就得到了一個時間復雜度 \(O(q \log n)\) 的做法。

代碼

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
#define mid ((l + r) >> 1)
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 5e5 + 5,M = 3.2e4 + 5,base = 13331;
ull h[N],mi[N];
vector<int> v[N];
bool vis[N];
vector<int> pri;
int d[N];
void euler(){
	for(int i=2;i<N;i++){
		if(!vis[i]){
			d[i] = i;
			pri.push_back(i);
		}
		for(int j=0;j<pri.size() && i * pri[j] < N;j++){
			vis[i * pri[j]] = true;
			d[i * pri[j]] = pri[j];
			if(i % pri[j] == 0){
				break;
			}
		}
	}
}
ull get(int l,int r){
	return h[r] - h[l - 1] * mi[r - l + 1];
}
bool chk(int l,int r,int k){
	if(!k) return false;
	return get(l,r - k) == get(l + k,r);
}
int calc(int l,int r){
	int len = r - l + 1;
	int res = len,now = len; 
	while(now > 1){
		if(chk(l,r,res / d[now])){
			res /= d[now];
		}
		now /= d[now];
	}
	return res;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	euler();
	int n;
	cin>>n;
	string s;
	cin>>s;
	s = " " + s;
	mi[0] = 1;
	for(int i=1;i<s.size();i++){
		mi[i] = mi[i - 1] * base;
		h[i] = h[i - 1] * base + s[i];
	}
	int q;
	cin>>q;
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<calc(a,b)<<'\n';
	}
	return 0;
}