算法-GCD和LCM问题 [英] Algorithm - GCD and LCM problems
问题描述
此问题的输入是正整数和单个正整数k的数组A.如果k在下面定义的集合S中，则程序的输出为True，否则为False.
Input for this problem is an array A of positive integers and single positive integer k. The output of the program is True if k is in the set S defined below, False otherwise.
如下定义集合S:
- 如果x在A中，那么x在S中
- 如果x和y在S中，则GCD(x，y)在S中.
- 如果x和y位于S中，则LCD(x，y)位于S中
附加约束:对于A中的每个x，数组A的大小为≤50000，k≤10 12 和x≤10 12 .程序必须返回在1秒或更短的时间内得到答案.
Additional constraints: The size of the array A is ≤ 50000, k ≤ 1012, and x ≤ 1012 for each x in A. The program must return an answer in 1 second or less.
我没有什么好主意.我唯一想到的就是找到数组中任意一对整数的GCD和LCM，然后可以扩大集合S.但是随着S的扩展，新的整数将成为新的对，以制造更多的GCD和LCM.
I don't have any good idea. The only thing I can think of is to find GCD and LCM of any pair of integers in the array, then I can enlarge the set S. But as the S is expanding, the new integers will be new pairs to make more GCDs and LCMs.
我希望你们能帮助我.我已经坚持了很长时间.
I hope you guys help me. I have been stuck with this for long.
更新:
例如，给出的数组为A = {10，12，15};
For instance an array is given is A= { 10, 12, 15 };
正如我们所提到的，S = {...，10，12，15，...}
As we have mentioned, the S = {..., 10, 12, 15, ...}
我们知道10、12、15在S中.因此，他们的GCD和LCM也在S中.意思是:
We know that 10, 12, 15 is in S. So their GCD and LCM is in S too. Which means:
GCD(10，12)= 2 in S
GCD(10, 12) = 2 in S
GCD(10，15)= 5 in S
GCD(10, 15) = 5 in S
GCD(12，15)= 3 in S
GCD(12, 15) = 3 in S
LCM(10，12)= 60 in S
LCM(10, 12) = 60 in S
...
最后:
S = {1，2，3，5，10，12，15，30，60}
S = { 1, 2, 3, 5, 10, 12, 15, 30, 60 }
推荐答案
将因子k分解为不同素数的幂.对于每个这样的主要功率因数，计算其为除数的所有阵列元素的GCD.如果(且仅)某些GCD不是k的除数，则S不包含k.
Factor k into powers of distinct primes. For each such prime power factor, compute the GCD of all array elements of which it is a divisor. If (and only if) some GCD is not a divisor of k, then S does not contain k.
正确性证明涉及以下事实:正整数是带有算子GCD和LCM的分布格.
The correctness proof involves the fact that the positive integers are a distributive lattice with operators GCD and LCM.
这篇关于算法-GCD和LCM问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
