今天上课讲的题。
做法就直接枚举约数，或者说分解质因数。后者可以预处理到log。
判循环也比较开心。直接用一些奇奇怪怪的字符串的性质就好了。
看来字符串很博大精深啊。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long qw;
typedef pair <int, qw> hstrv;
#define _l (long long int)
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
const int maxn = 500009;
const int base = 257;
const int hmod = 1000000093;
int pba[maxn];
qw pbb[maxn];
struct hstr {
int a[maxn];
qw b[maxn];
int init(char* x) {
a[0] = 0;
b[0] = 0;
int n = 1;
for (++ x; *x; ++ x, ++ n) {
a[n] = (_l a[n - 1] * base + *x) % hmod;
b[n] = b[n - 1] * base + *x;
}
return n - 1;
}
inline hstrv range(int l, int r) {
int x = ((a[r] - _l a[l - 1] * pba[r - l + 1]) % hmod + hmod) % hmod;
qw y = b[r] - b[l - 1] * pbb[r - l + 1];
return hstrv(x, y);
}
};
char a[maxn];
hstr ha;
int n, q;
int pn[maxn], tp, mf[maxn];
bool pr[maxn];
void pre() {
pba[0] = 1;
pbb[0] = 1;
for (int i = 1; i < maxn; ++ i) {
pba[i] = _l pba[i - 1] * base % hmod;
pbb[i] = pbb[i - 1] * base;
}
memset(pn, 0, sizeof(pn));
tp = 0;
for (int i = 2; i <= n; ++ i) {
if (!pr[i]) {
pn[tp ++] = i;
mf[i] = i;
}
for (int j = 0; j < tp && i * pn[j] <= n; ++ j) {
pr[i * pn[j]] = 1;
mf[i * pn[j]] = pn[j];
if (i % pn[j] == 0)
break;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
pre();
scanf("%s", a + 1);
ha. init(a);
readInt(q);
while (q --) {
int l, r, s;
readInt(l);
readInt(r);
s = r - l + 1;
for (int i = s, j; i > 1; i /= mf[i]) {
j = s / mf[i];
if (ha. range(l, r - j) == ha. range(l + j, r))
s = j;
}
printf("%d\n", s);
}
}