algorithm - 算法 - GCD 和 LCM 问题

Question

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

定义集合 S 如下：

1. 如果 x 在 A 中，则 x 在 S 中
2. 如果 x 和 y 在 S 中，则 GCD(x,y) 在 S 中
3. 如果 x 和 y 在 S 中，则 LCD(x,y) 在 S 中

附加约束：数组 A 的大小为 ≤ 50000，k ≤ 10 ¹²，并且对于 A 中的每个 x，x ≤ 10 ^12。程序必须在 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) = 2 在 S

GCD(10, 15) = 5 in S

GCD(12, 15) = 3 在 S

LCM(10, 12) = 60 英寸

...

最后：

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

Answer 1

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

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