算法 - GCD 和 LCM 问题

Question

此问题的输入是正整数数组 A 和单个正整数 k。如果 k 在下面定义的集合 S 中，程序的输出为 True，否则为 False。

定义集合S如下:

<醇>

如果x在A中那么x在S中

如果x和y在S中，则GCD(x,y)在S中

如果x和y在S中，则LCD(x,y)在S中

附加约束:数组A的大小≤50000，k≤10¹²，对于A中的每个x，x≤10¹²。程序必须返回在 1 秒或更短时间内回答。

我没有什么好主意。我唯一能想到的就是找到数组中任意一对整数的GCD和LCM，然后我可以扩大集合S。但是随着S的扩大，新的整数将成为新的对，从而产生更多的GCD和LCM .

希望大家帮帮我。我长期以来一直坚持这个问题。

更新:

例如给定的数组是 A= { 10, 12, 15 };

正如我们所提到的，S = {..., 10, 12, 15, ...}

我们知道10、12、15在S，所以他们的GCD和LCM也在S。这意味着:

GCD(10, 12) = S 中的 2

GCD(10, 15) = S 中的 5

GCD(12, 15) = S 中的 3

LCM(10, 12) = S 中的 60

...

最后:

S = { 1, 2, 3, 5, 10, 12, 15, 30, 60 }

Answer 1

将 k 分解为不同素数的幂。对于每个这样的质数功率因数，计算它作为除数的所有阵列元素的 GCD。如果(且仅当)某个 GCD 不是 k 的约数，则 S 不包含 k。

正确性证明涉及正整数是具有算子 GCD 和 LCM 的分配格这一事实。