正在给定大小N.您将提供的q查询的整数数组中的每个查询是由两个整数大号psented重新$ P $，R。你必须要找到的的GCD（最大公约数）不包括部分从范围从左至右包括

You are given an array A of integers of size N. You will be given Q queries where each query is represented by two integers L, R. You have to find the gcd(Greatest Common Divisor) of the array after excluding the part from range L to R inclusive

我的方法：

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);
}

但这种做法给我时间超限错误我怎样才能提高我的alogrithm

But This approach give me Time Limit Exceeded Error How can i improve my alogrithm

推荐答案

您可以precompute的GCD每个preFIX和后缀（姑且称之为 GCD preFIX 和 gcdSuffix ）的 O（N *登录MAX_A）时间（只需遍历从阵列从左到右，存储当前最大公约数，然后执行从右到左的相同的东西）。为（L，R）查询答案是 GCD（GCD preFIX [L - 1]，gcdSuffix [R + 1] ）（所以它是 O（日志MAX_A）每次查询操作）。总的时间复杂度为 O（（N + Q）*登录MAX_A）。我认为它应该是足够快。

You can precompute the gcd for each prefix and suffix(let's call it gcdPrefix and gcdSuffix) in O(n * log MAX_A) time(just iterate over your array from left to right and store the current gcd, then do the same thing from right to left). The answer for a (L, R) query is gcd(gcdPrefix[L - 1], gcdSuffix[R + 1])(so it is O(log MAX_A) operations per query). The total time complexity is O((n + q) * log MAX_A). I think it should be fast enough.