gcd 区间

通过动态规划，某一个区间 GCD 可由前一个子区间的 GCD 与最后一个元素GCD 得到，处理所有区间的最大公因数，然后直接查表输出结果。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    vector<vector<int>> f(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        f[i][i] = h[i]; // 单个元素的区间GCD为自身
    }

    for (int len = 1; len < n; len++) {
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            f[i][j] = __gcd(f[i][j-1], f[j][j]); // 递推
        }
    }
    while (m--) {
        int a, b;
        cin >> a >> b;
        cout << f[a-1][b-1] << '\n';
    }

    return 0;
}

时间复杂度：O(n2+m) 空间复杂度：O(n2)