CSP-S 提高级 · CSP 2026 提高级第一轮 第 17 题

【阅读程序2】

说明：保证 1 ≤ n ≤ 100000，每次查询满足 1 ≤ L ≤ R ≤ n，且数组 a 的元素均为正整数。

#include <iostream>
using namespace std;
int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];
int gcd(int x, int y) {
    if (y == 0) return x;
    return gcd(y, x % y);
}
int main() {
    cin >> n >> m;
    for (i = 1; i <= n; i++) cin >> a[i];
    t = 0;
    pw[0] = 1;
    for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;
    for (i = 1; i <= 100000; i++)
        if (pw[t + 1] >= i) lg[i] = t;
        else t++, lg[i] = t;
    for (i = 1; i <= n; i++)
        dp[i][0] = a[i];
    for (j = 1; j <= lg[n]; j++)
        for (i = 1; i + pw[j] - 1 <= n; i++) {
            dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]);
        }
    for (i = 1; i <= m; i++) {
        cin >> L >> R;
        cout << gcd(dp[L][lg[R-L+1]],dp[R-pw[lg[R-L+1]]+1][lg[R-L+1]]) << endl;
    }
    return 0;
}

这是"ST 表（稀疏表）+ gcd"：dp[i][j] 保存从 a[i] 开始连续 2^j 个数的最大公约数，预处理用倍增合并两半（第二半从 i + 2^(j−1) 起），查询时把区间拆成两段长度 2^k 的块取 gcd。lg[x] 是按 pw[t+1] >= i 生成的"长度 → 指数"映射。

把查询拆成"两段长度 2^k"误当成"刚好拼满区间"——两段可以重叠、不可以留缝；lg 的生成条件用 > 还是 >= 会影响第 27 题（正确答案对应 x ∈ [33, 64]）；区间长度为 1 时输出等于 a[L] 而不是 0。

程序分析

int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }   // 辗转相除

int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];
...
pw[0] = 1;  for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;   // pw[j] = 2^j
t = 0;
for (i = 1; i <= 100000; i++)
    if (pw[t + 1] >= i) lg[i] = t;      // 求"长度 i 该用哪个指数"
    else t++, lg[i] = t;
for (i = 1; i <= n; i++) dp[i][0] = a[i];                       // 长度为 1 的块
for (j = 1; j <= lg[n]; j++)
    for (i = 1; i + pw[j] - 1 <= n; i++)
        dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]); // 倍增合并两半
for (i = 1; i <= m; i++) {
    cin >> L >> R;
    cout << gcd(dp[L][lg[R - L + 1]], dp[R - pw[lg[R - L + 1]] + 1][lg[R - L + 1]]) << endl;
}

算法主线：ST 表求区间 gcd

• 状态：dp[i][j] = gcd(a[i], a[i+1], …, a[i + 2ʲ − 1])，即"从 i 开始连续 2ʲ 个数的 gcd"；
• 转移：长度为 2ʲ 的块 = 两个长度为 2ʲ⁻¹ 的块合并 → dp[i][j] = gcd(dp[i][j-1], dp[i + 2^(j-1)][j-1])（这正是第 21 行，第二半的起点是 i + pw[j−1]）；
• 查询：区间 [L, R] 长度为 len，取 k = lg[len]，用两个长度 2^k 的块覆盖它：左块起点 L，右块起点 R − 2^k + 1。两块可以重叠（gcd 满足重复合并不影响结果），因此不要求 2·2^k 恰好等于 len，只需 ≥ len，这就是 lg 定义稍显"奇特"的原因。

第 22 题（判断）

n = 5，a = {4, 2, 6, 3, 9}，查询 L = 2、R = 5（区间 a[2..5] = {2, 6, 3, 9}，len = 4）：

• k = lg[4] = 1，2¹ = 2；
• 左块 dp[2][1] = gcd(a[2], a[3]) = gcd(2, 6) = 2；
• 右块起点 = 5 − 2 + 1 = 4，dp[4][1] = gcd(a[4], a[5]) = gcd(3, 9) = 3；
• 结果 gcd(2, 3) = 1 ✓

答案：A（正确） ✓

第 23 题（判断）

区间长度为 1 即 L = R，此时 k = lg[1] = 0，pw[0] = 1：

• 左块 dp[L][0] = a[L]；
• 右块起点 = R − 1 + 1 = R = L，也是 a[L]；

gcd(a[L], a[L]) = a[L]，所以输出一定等于 a[L]。 答案：A（正确） ✓

第 24 题（判断）

程序的输出是区间内所有数的最大公约数。gcd 一定不超过区间最小值（因为每个数都能被 gcd 整除），所以"输出结果一定不小于区间内的最小值"错误——正确说法是"不大于"。 举例：区间 {2, 6, 3, 9} 输出 1，而最小值是 2，1 < 2。 答案：B（错误） ✓

第 25 题（单选）

由状态定义，dp[i][j] 表示"从 a[i] 开始连续 2ʲ 个数"的最大公约数。 答案：B ✓ （A 把 2ʲ 读成 j；C 混淆了 i、j 的角色；D 把区间起点写成 1。）

第 26 题（单选）

建表是两层循环：外层 j 从 1 到 lg[n] ≈ log n，内层 i 从 1 到 n − 2ʲ + 1 ≈ n。每次转移只做一次 gcd（视作 O(1)），故总复杂度 Θ(n log n)。 答案：B ✓ （A 漏掉了 log 层；C Θ(n²) 是朴素区间 DP；D Θ(nm) 把查询次数当成了建表代价。）

第 27 题（单选）

lg[] 的生成规则是：t 从 0 开始，pw[t+1] >= i 成立则 lg[i] = t，否则 t 自增。等价地说，lg[i] = 满足 2^(t+1) ≥ i 的最小 t，即：

• lg[i] = 5 ⟺ 2⁵ = 32 ≥ i 不成立（t 必须 ≥ 5），而 2⁶ = 64 ≥ i 成立
• ⟹ 33 ≤ i ≤ 64

所以 x 的取值范围是 [33, 64]，共 32 个值。 答案：D ✓ （实测 lg[32] = 4、lg[33] = 5、lg[64] = 5、lg[65] = 6，与上述一致。C 的 [32, 63] 是把条件写成 pw[t+1] > i 才会得到的结果。）

本题小结

套路提示：ST 表的三个必看细节——① 状态里"2^j 个数"的倍增含义；② 转移时第二半的起点（i + 2^(j−1)，不是 i + 2ʲ − 1）；③ 查询时"两块允许重叠"的性质。理解了③，第 27 题这种"lg 的奇怪定义"就不再是难点。