CSP-S 2026 第一轮 第 24 题：程序（二）：任意一次查询的输出结果一定不小于该查询区间内的最小值

题目

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

任意一次查询的输出结果一定不小于该查询区间内的最小值。（ ）

选项

• √. 正确
• ×. 错误

答案

×

题解

选 ×，错误。

反例：数组为 \(a=[2,3]\)，查询区间为 \([1,2]\)。

根据代码，lg[2] = 0，所以输出为： ``cpp gcd(dp[1][0], dp[2][0]) = gcd(2, 3) = 1 ``

而区间最小值为 \(2\)，因此输出 \(1<2\)，不满足“一定不小于”。

关键：最大公约数是公约数，可能小于所有参与运算的正整数。“最大”并不表示它比原来的数大。