CSP-S 2026 第一轮 第 25 题：程序（二）：对于 j≥1，数组 dp[i][j] 保存的是

题目

#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;
}

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

对于 $j \ge 1$，数组 dp[i][j] 保存的是（ ）。

选项

• A. 从 a[i] 开始连续 $j$ 个数的最大公约数
• B. 从 a[i] 开始连续 $2^{j}$ 个数的最大公约数
• C. a[i] 与 a[j] 的最大公约数
• D. 从 a[1] 到 a[i] 的最大公约数

答案

B

题解

答案是 B：从 a[i] 开始连续 \(2^j\) 个数的最大公约数。

关键看初始化和递推式：

``cpp dp[i][0] = a[i]; ``

这表示从 a[i] 开始，连续 \(2^0=1\) 个数的最大公约数。

又因为 pw[j - 1] = 2^(j - 1)，所以：

``cpp dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]); ``

是在合并两个相邻区间的最大公约数。每个区间有 \(2^{j-1}\) 个数，合起来就有 \(2^j\) 个数。

例如：

• dp[i][1]：a[i]、a[i+1] 这 2 个数的最大公约数。
• dp[i][2]：a[i] 到 a[i+3] 这 4 个数的最大公约数。

因此，对于程序中计算过的有效位置， \[ \boxed{dp[i][j]=\gcd(a[i],a[i+1],\ldots,a[i+2^j-1])}. \]