数组的 GCD

Question

给定一个大小为 N 的整数数组 A。你将得到 Q 个查询，其中每个查询由两个整数 L、R 表示。你必须在之后找到数组的 gcd（最大公约数）排除 L 到 R 范围内的部分

我的方法：

public static int gcd(int a ,int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

for(int j = 0; j < Q; j++) {
    int l = in.nextInt();
    int r = in.nextInt();
    ans = 0;
    for(int k = 1; k <= n; k++) {
        if(k < l || k > r) ans = gcd(a[k], ans);
    }
    System.out.println(ans);
}

但是这种方法给我超出时间限制的错误我怎样才能改进我的算法

Answer 1

您可以在 O(n * log MAX_A) 时间内为每个前缀和后缀（我们称之为 gcdPrefix 和 gcdSuffix）预先计算 gcd（只需从左到右遍历数组并存储当前的 gcd，然后从右到左做同样的事情）。 (L, R) 查询的答案是 gcd(gcdPrefix[L - 1], gcdSuffix[R + 1])（因此每个查询是 O(log MAX_A) 操作）。总时间复杂度为O((n + q) * log MAX_A)。我觉得应该够快了。

数组的 GCD

GCD of an array

java

algorithm

greatest-common-divisor