时间戳

首页 > 解决方案 > 给定一个整数 N 和一个整数 G，找到所有 GCD 大于 G 的元素 <=N 对

java - 给定一个整数 N 和一个整数 G，找到所有 GCD 大于 G 的元素 <=N 对

问题描述

给定一个整数 N 和另一个整数 G，找到所有整数对 (i,j) 使得 gcd (i,j) > G 其中 0<=i,j<=N。

最简单的解决方案是运行两个循环并检查每对的 gcd，这将导致 O(n^2) 复杂度。

我想到的第二种方法是从 G+1 到 N/2 运行循环，并且对于每个 i ，获取它的所有倍数。但这不会生成所有对。

        List<Pair<Integer, Integer>> ll = new LinkedList<>();
        for(int i=g+1;i<=n/2;i++){
            List<Integer> l = new LinkedList<>();
            for(int j=i+i;j<=n;j+=i){
                ll.add(new Pair<>(i, j));
            }
        }

第三种方法是考虑从 G+1 到 N 的所有元素，并为每个元素获取它们的所有除数 > G。

        List<Pair<Integer, Integer>> ll = new LinkedList<>();
        for(int j=g+1;j<=n;j++) {
            for (int i = g+1; i <= Math.sqrt(j); i++) {
                if (i != j && j % i == 0 && (j/i)!= j) {
                    if (j / i == i && i>g) // check if divisors are equal
                        ll.add(new Pair<>(i, j));
                    else {
                        if(i > g) ll.add(new Pair<>(i, j));
                        if (j / i > g) ll.add(new Pair<>(j / i, j));
                    }
                }
            }
        }

我正在寻找更优化的解决方案。请帮忙。

标签： javamathgreatest-common-divisor

解决方案

你可以用这个算法来生成你的对：从 G+1 开始，对于每个整数直到 N/2，创建一个小于 N 的乘数列表。例如，如果 G=3 和 N=19，你将开始和：

  • 4：4、8、12、16
  • 5：5、10、15
  • 6：6、12、18
  • 7：7、14
  • 8：8、16
  • 9：9、18

您需要通过选择任何配对（不包括双打）从该列表中进行配对：4:8、4:12、4:16、8:12、8:16、12:16、5:10、5 :15、10:15、6:12、6:18、12:18、7:14、9:18。您可以一次执行一组乘数，从 G+1 到 N/2。这段代码的复杂度是 O((N/2-G)*K)，其中 K 是乘数列表的长度，最多 N/(G+1)。您可以通过跳过已经出现在乘数列表中的数字来进一步改进这一点（例如，在我们的示例中我们不需要处理 8）。

生成它的代码很简单：

int n = 1000;
int g = 1;
boolean[] skipMultiplier = new boolean[n+1];
Set<Pair<Integer,Integer>> pairs = new HashSet<Pair<Integer,Integer>>();
for (int i=g+1; i<n/2+1 ;i++) {
    List<Integer> multipliers = new ArrayList<Integer>();
    for (int j=2; j< n/i+1 ; j++) {
        if (skipMultiplier[i]) {
            continue;
        }
        multipliers.add(i*j);
        skipMultiplier[i*j] = true;
        Pair<Integer,Integer> pair = new Pair<Integer,Integer>(i,i*j);
        pairs.add(pair);
    }
    for (int j=0; j<multipliers.size()-1; j++) {
        for (int k=j+1; k<multipliers.size(); k++) {
            Pair<Integer,Integer> pair = 
                new Pair<Integer,Integer> (multipliers.get(j), multipliers.get(k));
            pairs.add(pair);
        }
    }
}

推荐阅读