检查一个整数是否是给定集合中某些元素的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

CCD_ 13不是任何包含2个以上整数的群的GCD。答案是false

集合大小：<=100000

编辑：很抱歉举了一个错误的例子。这是我的错误。k = 3不是GCD（10，18）。但我想你可能知道这是15，对吧感谢您的回答、评论和贡献。我在下面投票选出了一个公认的答案。

Answer 1

1问题与示例不一致：

对于10、15、18：

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

2您的问题可以这样减少：

• k划分每个元素，所以划分它们=>新的"减少"集
• 如果k是某个子集的GCD，那么，相应的约简子集有1作为GCD（它们一起是素数）
• 这样我们就可以忘记k

3现在的问题是：给定一个集合，它是素在一起的元素的子集吗（或者用1作为GCD）

但是，如果从一个子集来看它是真的，那么它对所有元素都是真的。

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

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

Answer 2

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