题目分析

给定字符串 $S$，$q$ 次询问子串 $S[l:r]$ 的最短循环节长度。

循环节性质：若长度为 $len$ 的子串有循环节 $d$，则 $d$ 必须整除 $len$，且满足：

$$S[l:r-d] = S[l+d:r]$$

---

核心思路

1. 字符串哈希预处理

• 使用多项式哈希快速比较任意两个子串是否相等
• 预处理 $b^i \mod p$ 和前缀哈希值

2. 线性筛预处理

• 预处理每个数的最小质因子 $e[i]$
• 用于快速分解区间长度的质因数

3. 循环节判定

对于区间长度 $n = r-l+1$，初始答案 $ans = n$：

• 不断用 $n$ 的最小质因子 $p$ 尝试：
  • 如果 $ans/p$ 是循环节，则 $ans \gets ans/p$
• 继续分解 $n \gets n/p$

---

代码解析

// 线性筛预处理最小质因子
void init() {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) prime[++cnt] = i, e[i] = i;
        for (int j = 1; j <= cnt && prime[j] * i <= n; j++) {
            vis[prime[j] * i] = 1;
            e[prime[j] * i] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
    
    // 字符串哈希预处理
    for (int i = 1; i <= n; i++)
        h[i] = (1ll * h[i - 1] * b % p + s[i]) % p;
}

// 查询子串哈希值
int solve(int l, int r) {
    return (h[r] - 1ll * h[l - 1] * qpow[r - l + 1] % p + p) % p;
}

// 主查询逻辑
for (int l, r; q--;) {
    cin >> l >> r;
    n = r - l + 1, ans = n;
    
    while (n > 1) {
        int p = e[n];  // 最小质因子
        // 检查 ans/p 是否为循环节
        if (solve(l + ans / p, r) == solve(l, r - ans / p))
            ans /= p;
        n /= p;
    }
    
    cout << ans << '\n';
}

---

关键优化

1. 哈希比较技巧

检查 $d = ans/p$ 是否为循环节：

• 比较 $S[l:r-d]$ 和 $S[l+d:r]$ 是否相等
• 即去掉首尾各 $d$ 长度的部分后比较剩余部分

2. 质因数分解优化

• 利用最小质因子快速分解
• 从大到小尝试可能的循环节长度

3. 算法正确性

基于事实：最短循环节长度必须是 $n$ 的约数，且可以通过不断除以质因子得到。

---

复杂度分析

• 预处理：
  • 线性筛：$O(n)$
  • 哈希预处理：$O(n)$
• 每次查询：$O(\log n)$
  • 质因数分解最多 $O(\log n)$ 次
  • 每次哈希比较 $O(1)$

---

样例验证

输入：

8
aaabcabc
3
1 3
3 8
4 8

查询1 $(1,3)$："aaa"

• $n=3$，质因子3
• 检查 $ans=3/3=1$："aa" == "aa" ✓
• 输出：1

查询2 $(3,8)$："abcabc"

• $n=6$，质因子2,3
• 先检查 $6/2=3$："abc" == "abc" ✓，$ans=3$
• 再检查 $3/3=1$：不满足
• 输出：3

查询3 $(4,8)$："bcabc"

• $n=5$，质因子5
• 检查 $5/5=1$：不满足
• 输出：5

输出：

1
3
5

---

总结

该解法通过：

1. 字符串哈希实现 $O(1)$ 子串比较
2. 线性筛预处理质因数分解
3. 贪心分解从大到小尝试循环节

高效解决了大规模查询的最短循环节问题，时间复杂度 $O(n + q\log n)$。