CSP-S 2026 第一轮 第 22 题：程序（二）：当 n=5，a=4,2,6,3,3

题目

#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$ 的元素均为正整数。

当 $n=5$，$a={4, 2, 6, 3, 3}$，且仅有一次查询 $L=2, R=5$ 时，输出为 1。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

选 √，正确，输出确实为 1。

注意：这里计算 lg 时用的是 >=，所以 lg[4] = 1，不是通常的 \(\lfloor\log_2 4\rfloor=2\)。

查询区间长度为 \(5-2+1=4\)，代入输出语句： ``cpp gcd(dp[2][1], dp[5 - pw[1] + 1][1]) = gcd(dp[2][1], dp[4][1]) ``

其中 pw[1] = 2，而 dp[i][1] 表示从位置 \(i\) 开始、长度为 2 的区间的最大公约数：

• dp[2][1] = gcd(2, 6) = 2
• dp[4][1] = gcd(3, 3) = 3

因此最终输出为 \(\gcd(2,3)=\boxed{1}\)。