C++14(g++5.4) 解法, 执行用时: 1161ms, 内存消耗: 20452K, 提交时间: 2019-12-08 16:07:00

#include<bits/stdc++.h>
using namespace std;
const unsigned P = 1e9+7;
const int MAXN = 5e5+7;
unsigned H[MAXN];
unsigned B[MAXN];
char s[MAXN];
int primes[MAXN];
int p_sz;
int factor[MAXN];
int readInt() {
  int a = 0;
  char c;
  while (isdigit(c = getchar()))  {
    a = a * 10 + c - '0';
  }
  return a;
}
int main() {
  int n; scanf("%d", &n);
  scanf("%s", s);
  for (int i = 2; i <= n; i++) {
    if (!factor[i]) primes[p_sz++] = i, factor[i] = i;
    for (int j = 0; j < p_sz; j++) {
      int p = primes[j];
      long long s = (long long) p * i;
      if (s > n) break;
      factor[s] = p;
      if (i % p == 0) break;
    }
  }

  for (int i = 0; i < n; i++) H[i+1] = H[i] * P + s[i];
  for (int i = 0; i <= n; i++) B[i] = i?B[i-1]*P:1;
  int q; scanf("%d", &q);
  while (q--) {
    int a, b; scanf("%d %d", &a, &b);
    int L = b - a + 1;
    int ans = L;
    while (L != 1) {
      int p = factor[L];
      while (L % p == 0) {
        int i = ans / p;
        if (H[a+ans-1] - H[a+i-1]*B[ans-i] == H[a+ans-i-1] - H[a-1]*B[ans-i])  {
          ans /= p, L /= p;
        } else break;
      }
      while (L%p== 0) L /= p;
    }
    printf("%d\n", ans);
  }
}

C++ 解法, 执行用时: 878ms, 内存消耗: 26232K, 提交时间: 2021-08-19 20:25:49

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500011;
long long e[MAXN]={1},h[MAXN];
long long Hash(int l,int r){l--;return h[r]-h[l]*e[r-l];}
int n,q,p[MAXN],f[MAXN];
char s[MAXN];
int main()
{
	scanf("%d%s%d",&n,s+1,&q);
	for(int i=1;i<=n;i++)e[i]=e[i-1]*31,h[i]=h[i-1]*31+(s[i]-'a'+1);
	for(int i=2;i<=n;i++)
		if(!f[i])
			for(int j=i;j<=n;j+=i)f[j]=1,p[j]=i;
	while(q--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		int len=b-a+1;
		for(int i=len;i>1;i/=p[i])
			if(Hash(a,b-len/p[i])==Hash(a+len/p[i],b))len/=p[i];
		printf("%d\n",len);
	}
}