改进关于GCD的方法

Question

您将获得一个大小为 N 的整数数组 A。您将获得 Q 查询，其中每个查询由两个整数 L、R 表示。您必须在排除范围 L 到 R 的部分后找到数组的 gcd（最大公约数N ≤ 10^6, 1 ≤ Q ≤ N,

我的方法：

计算前缀 GCD，然后加缀 GCD 并返回答案。

法典：

public static int gcd(int a , int b){
    
    
    if(b==0) return a;
    
    return gcd(b,a%b);
}
for(int i=1;i<=n;i++){
        
        pre[i] = gcd(a[i],pre[i-1]);
    }
    suff[n]=a[n];
    for(int i=n-1;i>0;i--){
        
        suff[i] = gcd(a[i],suff[i+1]);
        
    }
    for(int i=0;i<t;i++){
        int l = in.nextInt();
        int r =in.nextInt();
        if(r!=n)
        System.out.println(gcd(pre[l-1],suff[r+1]));
        else
            System.out.println(pre[l-1]);
    }

问题：

这种方法给了我一个时间限制超过错误。如何改进我的解决方案？

Answer 1

这对我来说看起来大致正确，但它确实对一些查询做了很多工作。假设给你的 Q 查询都把 L 设置为 0;在这种情况下，您将不需要任何前缀计算。或者假设只有 1 个查询：您计算的前缀和后缀比您需要的要多。

我首先循环访问 Q 查询并找到 R 的最小值和 L 的最大值。这将使您能够计算回答这些查询所需的前缀和后缀。

加速的另一个潜在领域是您的gcd功能，您尚未向我们展示。

顺便说一下，当 L 为 0 时，您的代码当前不起作用。它将尝试检查pre[-1]。

编辑：gcd看起来不错。

Answer 2

让我们创建两个大小arr数组和大小N brr数组。其中arr[i]将存储输入数组中所有数字的 gcd 直到索引i（包括 i），brr[i] 将在索引i（包括 i）之后存储输入数组中所有数字的 gcd。

示例：arr[3]=gcd(A[0],A[1],A[2],A[3])和类似的brr将从相反的方向初始化。

现在假设查询是3,5您可以简单地输出gcd(arr[3],brr[5]) .