CSP-S 2026 第一轮 第 27 题：程序（二）：设 x 为一次查询的区间长度（即 x=R-L+1）

题目

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

设 $x$ 为一次查询的区间长度（即 $x=R - L+ 1$），则使得 lg[x] = 5 的 $x$ 的取值范围是（ ）。

选项

• A. $[16, 31]$
• B. $[17, 32]$
• C. $[32, 63]$
• D. $[33, 64]$

答案

D

题解

答案是 D．\([33,64]\)。

注意程序中的判断是 pw[t + 1] >= i，包含等号：

``cpp if (pw[t + 1] >= i) lg[i] = t; else { t++; lg[i] = t; } ``

其中 pw[k] = 2^k。看三个关键位置：

• 当 i = 32 时，t = 4，因为 pw[5] = 32 >= 32，所以 lg[32] = 4。
• 当 i = 33 时，32 >= 33 不成立，t 增加到 5，所以 lg[33] = 5。
• 此后直到 i = 64，都有 pw[6] = 64 >= i，所以 lg[i] = 5；到 i = 65 时才增加到 6。

因此： \[ \boxed{33\le x\le64} \]

这里不能直接套用常见的 lg[x] = ⌊log₂x⌋，要以代码中的比较符号为准。