检查一个整数是否是给定集合中某些元素的 GCD

Question

给定一组正整数和一个整数k。 集合中的所有元素 都可以被 k 整除。

如何检查k是否是集合中一些个元素的最大公约数？

我的想法：对于集合中的每个元素 a[i]，我将其除以 k。然后我得到集合中所有元素的 GCD（在我划分后改变了）。如果GCD等于1，那么k是集合中某些元素的GCD。

我做了一些测试用例，我看对了。但是在线法官不接受。请给我一个想法，或者检查我的算法并修复它。非常感谢。

再说清楚一点：

例如，a = {10, 15, 18}:

k = 5 是 GCD(10, 15)。答案是true

k = 3 是 GCD(15, 18)。答案是true

k = 1 是 GCD(10, 15, 18)。答案是true

k = 6 不是任何包含 2 个以上整数的组的 GCD。答案是 false

集的大小：<= 100000

编辑：抱歉举错了例子。这是我的错误。 k = 3 不是 GCD(10, 18)。但我想你可能知道这是 15，对吧。 :) 感谢您的回答、评论和贡献。我在下面投了一个接受的答案。

Answer 1

int gcd(int a, int b) {
  int c;
  while(a != 0) {
     c = a;
     a = b%a;
     b = c;
  }
  return b;
}

bool function(int[] a, int n, int k) {
    int numberOfGCD = 0;
    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(gcd(a[i], a[j]) == k) numberOfGCD++;
    return numberOfGCD > 1;
}

Answer 2

1 问题与例子不连贯：

对于 10、15、18：

3 不是 10 的约数，也不是 6
没有公约数

2 你的问题可以这样简化：

k 划分每个元素，所以划分它们 => new "reduced" set
如果k是某个子集的GCD，则对应的缩减子集有1作为GCD（它们一起是质数）
所以我们可以忘记 k

3 现在的问题是：给定一个集合，它是否是元素一起质数（或以 1 作为 GCD）的子集？

但如果它在一个子集中为真，则对所有元素都为真。

所以你的算法很好：取A1、A2和GCD，然后这个A3的GCD，...

如果在某个时候你得到1，它就结束了。

检查一个整数是否是给定集合中某些元素的 GCD

Check if an integer is GCD of some elements in a given set

algorithm

math

greatest-common-divisor