思路与算法

构造后缀数组及LCP。RMQ分成32项小块：每个右端点保存块内单调栈的32位掩码，区间最小值由掩码裁去左界之前的位置后取最低置位得到；整块最小值再建立小规模稀疏表。查询LCP只需两个块内最小值与中间整块RMQ。区间周期仍从长度L开始，按质因子p尝试d=answer/p，用LCP(l,l+d)≥L-d精确判断整段重复。

正确性说明

当d整除L时，整段可由长度d的前缀重复得到，等价于区间中相距d的所有字符相等，正好是该LCP判定。所有合法完整循环节长度都整除L。若更短合法循环节存在，它与当前合法周期的最大公约数也为合法周期，因此可以逐个删除质因子达到最短周期；删除失败的质因子不可能在后续成为必须删除的因子。精确LCP不引入哈希碰撞。 块内栈只删除被更晚且不大的元素支配的位置，因此对任何左界，删除左界前的栈位置后，第一个保留元素就是到当前右界的最小值。跨块区间分成左尾、若干整块、右头，三部分最小值相取即可。每次调用ctz的掩码均含右端点，绝不为0。

复杂度

SA构造O(n log n)，LCP和块内单调栈O(n)，整块稀疏表O((n/32)log(n/32))，最小质因子筛O(n log log n)。每个周期查询O(log L)，每次LCP的RMQ仍O(1)。空间O(n+(n/32)log(n/32))，全部数组和掩码初始化已计入。建好后释放不再使用的SA、原字符和整数输入副本；保留原64MiB与200万查询数据，不减点、不提高限制。

易错点

循环节必须整除区间长度，abcab的答案是5，不是3。判定比较的是整个原查询区间，不只是当前候选前缀。相同起点的LCP单独处理，长度1直接为1。独立答案直接构造重复串；满规模常串与五字母重复串用闭式周期验证。 首次原生第8点实际MLE（65552KiB），不能把预验证通过当作原生通过；本版采用分块掩码RMQ节省工作内存，须重新原生验收。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Suffix {
    int n;
    vector<int> sa, rank, height, logs;
    vector<vector<int>> st;
    vector<unsigned> mask;
    Suffix(const vector<int> &s)
        : n(s.size()), sa(n), rank(n), height(n), logs((n + 31) / 32 + 1), mask(n) {
        int alphabet = max(n, *max_element(s.begin(), s.end()) + 1);
        {
            vector<int> count(alphabet + 1), temp(n), nr(n);
            for (int x : s)
                ++count[x];
            for (int i = 1; i <= alphabet; ++i)
                count[i] += count[i - 1];
            for (int i = n - 1; i >= 0; --i)
                sa[--count[s[i]]] = i;
            int classes = 0;
            for (int i = 0; i < n; ++i) {
                if (i == 0 || s[sa[i]] != s[sa[i - 1]])
                    ++classes;
                rank[sa[i]] = classes - 1;
            }
            for (int k = 1; k < n && classes < n; k *= 2) {
                int at = 0;
                for (int i = max(0, n - k); i < n; ++i)
                    temp[at++] = i;
                for (int x : sa)
                    if (x >= k)
                        temp[at++] = x - k;
                fill(count.begin(), count.begin() + classes, 0);
                for (int x : temp)
                    ++count[rank[x]];
                for (int i = 1; i < classes; ++i)
                    count[i] += count[i - 1];
                for (int i = n - 1; i >= 0; --i) {
                    int x = temp[i];
                    sa[--count[rank[x]]] = x;
                }
                int nc = 0;
                for (int i = 0; i < n; ++i) {
                    int a = sa[i], b = i ? sa[i - 1] : -1;
                    if (i == 0 || rank[a] != rank[b] ||
                        (a + k < n ? rank[a + k] : -1) != (b + k < n ? rank[b + k] : -1))
                        ++nc;
                    nr[a] = nc - 1;
                }
                rank.swap(nr);
                classes = nc;
            }
        }
        int len = 0;
        for (int i = 0; i < n; ++i) {
            int z = rank[i];
            if (z == 0) {
                len = 0;
                continue;
            }
            int j = sa[z - 1];
            while (i + len < n && j + len < n && s[i + len] == s[j + len])
                ++len;
            height[z] = len;
            if (len)
                --len;
        }
        int blocks = (n + 31) / 32;
        vector<int> minimum(blocks, INT_MAX);
        unsigned active = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 32 == 0)
                active = 0;
            while (active) {
                int top = 31 - __builtin_clz(active);
                if (height[i - i % 32 + top] < height[i])
                    break;
                active &= ~(1U << top);
            }
            active |= 1U << (i % 32);
            mask[i] = active;
            minimum[i / 32] = min(minimum[i / 32], height[i]);
        }
        for (int i = 2; i <= blocks; ++i)
            logs[i] = logs[i / 2] + 1;
        st.push_back(move(minimum));
        for (int k = 1; (1 << k) <= blocks; ++k) {
            int size = blocks - (1 << k) + 1;
            st.emplace_back(size);
            for (int i = 0; i < size; ++i)
                st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
        vector<int>().swap(sa);
    }
    int smallMin(int l, int r) const {
        unsigned candidates = mask[r] & (~0U << (l % 32));
        return height[r - r % 32 + __builtin_ctz(candidates)];
    }
    int rangeMin(int l, int r) const {
        int first = l / 32, last = r / 32;
        if (first == last)
            return smallMin(l, r);
        int answer = min(smallMin(l, (first + 1) * 32 - 1), smallMin(last * 32, r));
        ++first;
        --last;
        if (first <= last) {
            int k = logs[last - first + 1];
            answer = min(answer, min(st[k][first], st[k][last - (1 << k) + 1]));
        }
        return answer;
    }
    int lcp(int a, int b) const {
        if (a == b)
            return n - a;
        int l = rank[a], r = rank[b];
        if (l > r)
            swap(l, r);
        return rangeMin(l + 1, r);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin >> n >> s;
    vector<int> a(s.begin(), s.end());
    Suffix sf(a);
    vector<int>().swap(a);
    string().swap(s);
    vector<int> spf(n + 1);
    for (int i = 2; i <= n; ++i)
        if (!spf[i])
            for (int j = i; j <= n; j += i)
                if (!spf[j])
                    spf[j] = i;
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        --l;
        int length = r - l, answer = length, z = length;
        while (z > 1) {
            int p = spf[z];
            while (z % p == 0)
                z /= p;
            while (answer % p == 0) {
                int candidate = answer / p;
                if (sf.lcp(l, l + candidate) >= length - candidate)
                    answer = candidate;
                else
                    break;
            }
        }
        cout << answer << '\n';
    }
}