检查整数是否为给定集中某些元素的GCD [英] Check if an integer is GCD of some elements in a given set
问题描述
给出一组正整数和一个整数k. 集合中的所有元素都可以被k整除.
Given a set of positive integers and an integer k. All of the elements in the set is divisible by k.
如何检查k是否是集合中一些元素的最大公约数?
How to check if k is greatest common divisor of some elements in the set?
我的想法:对于集合中的每个元素a[i]，我将其除以k.然后，我得到了集合中所有元素的GCD(除以后就改变了).如果GCD等于1，则k是集合中某些元素的GCD.
My idea: For every element a[i] in the set, I divide it by k. Then I get GCD of all of the element in the set (which was changed after I divided). If the GCD is equal to 1, then k is GCD of some elements in the set.
我已经做了一些测试用例，我看对了.但是在线法官不接受.请给我一个主意，或者检查我的算法并进行修复.非常感谢.
I have make some test cases and I see it right. But the online judge doesn't accept. Please give me an idea, or check my algorithm and fix it. Thank you very much.
让我说得更清楚:
例如，a = {10，15，18}:
For instance, a = {10, 15, 18}:
k = 5是GCD(10，15).答案是true
k = 5 is GCD(10, 15). Answer is true
k = 3是GCD(15，18).答案是true
k = 3 is GCD(15, 18). Answer is true
k = 1是GCD(10，15，18).答案是true
k = 1 is GCD(10, 15, 18). Answer is true
k = 6不是包含超过2个整数的任何组的GCD.答案是false
k = 6 is not GCD of any group which contains more than 2 integers. Answer is false
组的大小:< = 100000
Size of the set: <= 100000
对不起，您提供了错误的示例.是我的错k = 3不是GCD(10，18).但我想您可能知道这是15，对. :)感谢您的回答，评论和贡献.我在下面投票了一个可以接受的答案.
Sorry for giving a wrong example. It was my mistake. k = 3 is not GCD(10, 18). But I thought you might know this is 15 instead, right. :) Thanks for your answers, comments and contribution. I have voted an accepted answer below.
推荐答案
1这个问题与示例不一致:
10、15、18:
- 3不是10的除数，也不是6
- 没有共同的除数
2您的问题可以这样减少:
- k划分每个元素，因此划分它们=>新的精简"集
- 如果k是某个子集的GCD，则相应的约简子集的GCD为1(它们是素数)
- 所以我们可以忘记k
3现在的问题是:给定一个集合，它是元素的素子集在一起(还是1作为GCD)?
但如果在子集中为true，则对所有元素都是true.
but if it is true from a subset, it is true for all elements.
所以您的算法很好:先取A1，A2和GCD，然后取A3的GCD，...
So your algorithm is good: take A1, A2, and GCD, then GCD of this an A3, ...
如果在某个时候您得到1，则表示已完成.
If at some point you get 1, it is finished.
这篇关于检查整数是否为给定集中某些元素的GCD的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
