laekov

今天上课讲的题。

做法就直接枚举约数，或者说分解质因数。后者可以预处理到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);

}

}