CSP-S 2026 第一轮 第 26 题：程序（二）：若把一次求最大公约数的运算视为 O(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$ 的元素均为正整数。

若把一次求最大公约数的运算视为 $O(1)$，则第 17—22 行建表过程的时间复杂度为（ ）。

选项

• A. $Θ(n)$
• B. $Θ(n log n)$
• C. $Θ(n^{2})$
• D. $Θ(mn)$

答案

B

题解

选 B．\(\Theta(n\log n)\)。

建表的核心是这两层循环：

``cpp for (j = 1; j <= lg[n]; j++) for (i = 1; i + pw[j] - 1 <= n; i++) dp[i][j] = gcd(...); ``

因为 pw[j] = 2^j，所以：

• 外层 j 共执行约 \(\log_2 n\) 轮。
• 固定 j 时，内层条件等价于 \(i\le n-2^j+1\)，执行 \(n-2^j+1\) 次。
• 每次求最大公约数按题意视为 \(O(1)\)。

令 \(k=lg[n]\)，总操作次数为 \[ \sum_{j=1}^{k}(n-2^j+1) =k(n+1)-(2^{k+1}-2). \] 其中 \(k=\Theta(\log n)\)，而 \(2^{k+1}=\Theta(n)\)，因此总时间复杂度为 \[ \boxed{\Theta(n\log n)}. \]

直观理解：建表有约 \(\log n\) 层，其中绝大多数层都要处理与 \(n\) 同数量级的位置。查询次数 \(m\) 不影响建表复杂度。