题解 | #区间GCD#

题目链接

题目描述

给定一个包含 $N$ 个正整数的数组 $A$ 。有 $Q$ 次询问，每次询问给定一个下标区间 $[l, r]$ ，要求输出 $A[l \dots r]$ 中所有元素的最大公因数 (GCD)。

解题思路

本题要求我们高效地回答关于静态数组的区间查询。具体来说，是查询区间内所有元素的最大公因数 (GCD)。

一个朴素的方法是，对于每次查询 $[l, r]$ ，都遍历从 $l$ 到 $r$ 的所有元素并依次计算它们的 GCD。单次查询的时间复杂度为 $O((r-l+1) \cdot \log(\max(A)))$ ，其中 $\log$ 项是计算 GCD 的开销。在有 $Q$ 次查询的情况下，总时间复杂度会达到 $O(N \cdot Q \cdot \log(\max(A)))$ ，这对于 $N, Q \le 10^5$ 的数据规模来说是无法接受的。

为了优化查询，我们需要一种能在更短时间内处理区间查询的数据结构。注意到 GCD 运算满足结合律，即 $\text{gcd}(a, b, c) = \text{gcd}(\text{gcd}(a, b), c)$ 。此外，GCD 运算还满足可重复贡献性，即一个元素在区间 GCD 计算中出现多次不会影响最终结果（例如 $\text{gcd}(a,b,c) = \text{gcd}(\text{gcd}(a,b), \text{gcd}(b,c))$ ）。

对于满足可重复贡献性的静态区间查询问题，稀疏表 (Sparse Table, ST) 是一种非常高效的数据结构。ST 表通过 $O(N \log N)$ 的预处理，可以实现 $O(1)$ 的单次查询（严格来说是 $O(\log(\max(A)))$ ，因为最后要算一次 GCD，但通常视为常数时间）。

ST 表的构建与查询：

预处理：
- 我们创建一个二维数组 st[i][j]，表示数组 $A$ 中从下标 $i$ 开始、长度为 $2^j$ 的子区间的 GCD 值。
- 基础状态 ( $j=0$ )：st[i][0] = A[i]，即长度为 $1$ 的区间的 GCD 就是其本身。
- 递推关系：st[i][j] = gcd(st[i][j-1], st[i + 2^{j-1}][j-1])。这表示，一个长度为 $2^j$ 的区间的 GCD，等于其左半部分（长度为 $2^{j-1}$ ）和右半部分（长度也为 $2^{j-1}$ ）区间的 GCD 的最大公因数。
查询：
- 对于一个查询区间 $[l, r]$ ，其长度为 $\text{len} = r - l + 1$ 。
- 我们找到一个最大的整数 $k$ ，使得 $2^k \le \text{len}$ 。这可以通过预计算对数表或直接计算 k = log2(len) 得到。
- 由于 GCD 的可重复贡献性，区间 $[l, r]$ 的 GCD 可以由两个长度为 $2^k$ 的、可能重叠的子区间 $[l, l+2^k-1]$ 和 $[r-2^k+1, r]$ 的 GCD 计算得出。
- 因此，查询结果为 gcd(st[l][k], st[r - 2^k + 1][k])。

通过这种方法，我们可以高效地解决本题。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 计算最大公因数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    // 优化输入输出以避免超时
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 预处理ST表
    int log_n = floor(log2(n)) + 1;
    vector<vector<int>> st(n, vector<int>(log_n));

    for (int i = 0; i < n; ++i) {
        st[i][0] = a[i];
    }

    for (int j = 1; j < log_n; ++j) {
        for (int i = 0; i + (1 << j) <= n; ++i) {
            st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }

    // 预处理log值，用于O(1)查询
    vector<int> log_table(n + 1);
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }

    // 回答查询
    for (int k = 0; k < q; ++k) {
        int l, r;
        cin >> l >> r;
        --l; --r; // 转换为0-based
        int len = r - l + 1;
        int j = log_table[len];
        int result = gcd(st[l][j], st[r - (1 << j) + 1][j]);
        cout << result << endl;
    }

    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.lang.Math;

public class Main {
    // 计算最大公因数
    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader进行快速I/O
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(stk.nextToken());
        int q = Integer.parseInt(stk.nextToken());

        int[] a = new int[n];
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) {
            a[i] = Integer.parseInt(stk.nextToken());
        }

        // 预处理ST表
        int logN = (int) (Math.log(n) / Math.log(2)) + 1;
        int[][] st = new int[n][logN];

        for (int i = 0; i < n; ++i) {
            st[i][0] = a[i];
        }

        for (int j = 1; j < logN; ++j) {
            for (int i = 0; i + (1 << j) <= n; ++i) {
                st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
        
        // 预处理log值，用于O(1)查询
        int[] logTable = new int[n + 1];
        logTable[1] = 0;
        for (int i = 2; i <= n; i++) {
            logTable[i] = logTable[i / 2] + 1;
        }

        // 回答查询，并使用StringBuilder优化输出
        StringBuilder sb = new StringBuilder();
        for (int k = 0; k < q; ++k) {
            stk = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(stk.nextToken());
            int r = Integer.parseInt(stk.nextToken());
            l--; r--; // 转换为0-based
            int len = r - l + 1;
            int j = logTable[len];
            int result = gcd(st[l][j], st[r - (1 << j) + 1][j]);
            sb.append(result).append("\n");
        }
        System.out.print(sb.toString());
    }
}

import math
import sys

# 因输入量大，需要使用 sys.stdin.readline() 以避免超时
def solve():
    n, q = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))

    # 预处理ST表
    log_n = n.bit_length()
    st = [[0] * log_n for _ in range(n)]

    for i in range(n):
        st[i][0] = a[i]

    for j in range(1, log_n):
        for i in range(n - (1 << j) + 1):
            st[i][j] = math.gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1])
    
    # 预处理log值，用于O(1)查询
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i >> 1] + 1

    # 回答查询，并收集结果后统一输出以提高效率
    results = []
    for _ in range(q):
        l, r = map(int, sys.stdin.readline().split())
        l -= 1
        r -= 1
        length = r - l + 1
        k = log_table[length]
        result = math.gcd(st[l][k], st[r - (1 << k) + 1][k])
        results.append(str(result))
    
    print("\n".join(results))

solve()

算法及复杂度

算法：稀疏表 (Sparse Table)
时间复杂度：预处理 ST 表的时间复杂度为 $O(N \log N)$ （每次 GCD 计算的对数因子通常视为常数）。每次查询的时间复杂度为 $O(1)$ （同理，GCD 计算视为常数）。因此，总时间复杂度为 $O(N \log N + Q)$ 。
空间复杂度： $O(N \log N)$ ，用于存储 ST 表。