如何计算具有某些约束的数组中每个索引的 GCD

Question

给定一个 1 索引数组 A，大小为 N，任意数组之间的距离 2 这个数组的索引 i 和 j 由 |i−j 给出|。现在，根据这些信息，我需要为每个索引 i (1≤i≤N) 找到一个索引 j ，使得1≤j≤N，i≠j，并且GCD(A[i] ,A[j])>1.

如果一个索引i有多个这样的候选项，必须找到索引j，使得[=24]之间的距离=]i 和 j 是最小的。如果还有多个候选，则打印满足上述约束条件的最小j

Example: Array(A) 2 3 4 9 17

输出：3 4 1 2 -1

注意：数组大小最大可达 2*10^5。每个数组元素可以取最大值 2*10^5 和最小值 1.

我最多1秒就能算出来

这是我的代码，但是它超过了时间限制。有什么办法可以优化吗

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class GCD {


public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine().trim());
    int[] a = new int[n+1];
    StringBuilder sb =new StringBuilder("");
    String[] array = br.readLine().trim().split(" ");

    for(int i=1; i<=n; i++){
        a[i] = Integer.parseInt(array[i-1]);
    }

    int c,d;
l1: for(int i=1; i<=n; i++){
        c = i-1;
        d = i+1;
        while((c>0||d<=n)){
            if(c>0){
                if(GCD(a[i],a[c])>1){
                    sb.append(c+" ");
                    continue l1;
                }
            }
            if(d<=n){   
                if(GCD(a[i],a[d])>1){
                    sb.append(d+" ");
                    continue l1;
                }   
            }
            c--;
            d++;
        }

         sb.append("-1 ");
    }
    System.out.println(sb);
}


    static long GCD(int a, int b){
        if(b==0)
           return a;
        return GCD(b, a%b);
    }

}

Answer 1

到运行这个不到1秒，你的算法应该是θ(N)或者θ(N * log(N))，N<2*10^5。一种方法可以是：

让我们在数组的 1 次迭代中找到所有数字中除 1 之外的所有因数。复杂度 = θ(N) * θ(GCD) = θ(N * log(N))
制作一个散列图，键 = 我们刚刚找到的因子，值 = 输入中元素索引的排序数组，它们是因子。（哈希图中的数组是按顺序排列的，所以不需要显式排序。因子数<θ（log（N）））复杂度= θ（N * log（N））
现在我们遍历元素，在每个元素中，遍历因子，对于每个因子，我们使用二进制搜索从散列图中找到该因子在最近索引中的位置。我们 select 每个元素的所有因素的最接近值，并将其作为答案。复杂度 = θ (N * log(N) * log(log(N))).

Answer 2

你知道问题可以在一秒钟内解决。你知道数组可以有 200,000 个元素。 200,000 个元素与 200,000 个元素进行比较需要 400 亿次比较。如果幸运的话，您的计算机每秒可执行 30 亿次操作。您会看到将 200,000 个元素与 200,000 个元素进行比较是行不通的。（在所有数组元素都等于 1 的简单情况下会发生这种情况）。因此，优化您的代码无济于事。

因此，请将您的注意力从提出问题的方式转移开。它要求找到 j 以便 gcd (a [i], a [j]) != 1。它真正的意思是找到 j 使得 a[j] 与 a[i] 有一个共同的质因数。并且 j 需要是最大的 j < i 或最小的 j > i。

人数不多，不到20万。所以你可以很快找到 a [i] 的所有不同的质因数。

所以首先你创建一个数组"index"：对于每个质数 p <= 200,000，索引 [p] 是你检查的最后一个数组元素 a [j] 的索引 j因子 p，如果没有找到则为 -1。您还创建了一个数组 "solution"：对于您检查的每个 i，它包含迄今为止最接近的数字或 -1。

遍历 i = 1 到 n 的数组：对于每个 a [i]，找出所有质因数。对于每个因子 p：如果 j = index [p] > 0 那么 a [j] 也可以被 p 整除，所以 gcd (a [i], a [j]) > 1。这样做你得到最大的 j < i with gcd (a [i], a [j]) > 1。当你找到素因子时，还要更新数组索引。

但是如果你发现a[i]和a[j]有一个共同的因素，那么你为j存储的解决方案可能是错误的，因为它只考虑了小于j的索引，所以也更新解决方案.伪代码：

Create array "index" filled with -1.
Create array "solution" filled with -1.

for all i
    for all prime factors p of a [i]
        let j = index [p]
        index [p] = j
        if j >= 0
            if solution [i] = -1
                solution [i] = j
            else if j > solution [i]
                solution [i] = j

            if solution [j] = -1
                solution [j] = i
            else if solution [j] < j && i-j < j - solution [j]
                solution [j] = i

print solution

可以看出，有公因数的数组元素相距多远根本无关紧要。执行时间是一个非常小的乘以素数因子的数量，再加上寻找因子的时间，如果所有元素都是大素数，这是最糟糕的。因此，您需要做的就是在 3-4 微秒内找到小于 200,000 的任意数字的所有因数。应该很容易。在开始之前，您可以创建最多 500 个素数的 table。

如何计算具有某些约束的数组中每个索引的 GCD

How to calculate GCD for every index in array with some constraints

arrays

algorithm

greatest-common-divisor