用快读

这是一份 TLE 的代码：

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
using ll=long long;

ll g[500005];
bool vis[500005];
vector<ll> pri;

ull base[500005];
ull pre[500005];
int n,t;
char str[500005];

inline ull get_hash(int l,int r){
	return pre[r] - pre[l-1] * base[r-l+1];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie();
	cin>>n>>str+1>>t; 
	for (ll i = 2; i <= n; i++) {
		if (!vis[i])
			pri.push_back(i), g[i] = i;
		for (int j = 0; j < pri.size() && pri[j] * i <= n; j++) {
			vis[pri[j]*i] = true, g[pri[j]*i] = pri[j];
			if (i % pri[j] == 0)
				break;
		}
	}
	base[0]=1ull;
	for(int i = 1; i<=n; i++){
		base[i]=base[i-1]*29ull;
		pre[i]=pre[i-1]*29ull+str[i];
	}
	register int l,r;
	register ll ans,rans;
	while(t--){
		cin>>l>>r;
		ans=rans=r-l+1;
		while(rans>1){
			if(get_hash(l+ans/g[rans],r)==get_hash(l,r-ans/g[rans])){
				ans/=g[rans];
			}
			rans/=g[rans];
		}
		cout<<ans<<'\n';
	}
	return 0;
}

这是一份 AC 的代码：

#include <bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
using ll=long long;

template<typename T> inline void read(T &x) {
	x = 0; T k = 1; char in = getchar();
	while (!isdigit(in)) { if (in == '-') k = -1; in = getchar(); }
	while (isdigit(in)) x = x * 10 + in - '0', in = getchar();
	x *= k;
}

ll g[500005];
bool vis[500005];
vector<ll> pri;

ull base[500005];
ull pre[500005];
int n,t;
char str[500005];

inline ull get_hash(int l,int r){
	return pre[r] - pre[l-1] * base[r-l+1];
}

int main(){
	read(n);
	cin>>str+1;
	read(t);
	for (ll i = 2; i <= n; i++) {
		if (!vis[i])
			pri.push_back(i), g[i] = i;
		for (int j = 0; j < pri.size() && pri[j] * i <= n; j++) {
			vis[pri[j]*i] = true, g[pri[j]*i] = pri[j];
			if (i % pri[j] == 0)
				break;
		}
	}
	base[0]=1ull;
	for(int i = 1; i<=n; i++){
		base[i]=base[i-1]*29ull;
		pre[i]=pre[i-1]*29ull+str[i];
	}
	register int l,r;
	register ll ans,rans;
	while(t--){
		read(l),read(r);
		ans=rans=r-l+1;
		while(rans>1){
			if(get_hash(l+ans/g[rans],r)==get_hash(l,r-ans/g[rans])){
				ans/=g[rans];
			}
			rans/=g[rans];
		}
		cout<<ans<<'\n';
	}
	return 0;
}