1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<cstdio>
using namespace std;
#define re register
#define int long long
const int MAXn = 5e5;
const int BASE = 107;
const int MOD = 1e9 + 7;
template <class T>
inline void read(T &a) {
register char c;while (c = getchar(), c < '0' || c >'9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);}a = x;
}
int n, m, cntp, p[MAXn + 10], minpf[MAXn + 10];
bool notp[MAXn + 10];
void LS(int up) {
notp[1] = 1;
for (int i = 2; i <= up; ++i) {
if (!notp[i]) {
p[++cntp] = i;
minpf[i] = i;
}
int up2 = up / i;
for (int j = 1; j <= cntp && p[j] <= up2; ++j) {
notp[i * p[j]] = 1;
minpf[i * p[j]] = p[j];
if (!(i % p[j])) {
break;
}
}
}
}
int hashpre[MAXn + 10], poww[MAXn + 10];
inline int hash(int l, int r) {
return ((hashpre[r] - hashpre[l - 1] * poww[r - l + 1]) % MOD + MOD) % MOD;
}
char str[MAXn + 10];
signed main() {
read(n);
LS(n);
scanf("%s", str + 1);
for (int i = 1; i <= n; ++i) {
hashpre[i] = (hashpre[i - 1] * BASE + str[i] - 'a') % MOD;
}
poww[0] = 1;
for (int i = 1; i <= n; ++i) {
poww[i] = (poww[i - 1] * BASE) % MOD;
}
read(m);
for (re int i = 1; i <= m; ++i) {
int l, r, len, ans;
read(l), read(r);
ans = len = r - l + 1;
if (hash(l + 1, r) == hash(l, r - 1)) {
printf("1\n");
} else {
while (len > 1) {
if (hash(l + ans / minpf[len], r) == hash(l, r - ans / minpf[len])) {
ans /= minpf[len];
}
len /= minpf[len];
}
printf("%lld\n", ans);
}
}
}
|
