这个问题的输入是一个由正整数和单正整数k组成的数组A。如果k在下面定义的集合S中，则程序的输出为True，否则为False。
定义集合如下：
如果x在a中，那么x在s中
如果x和y在S中，则GCD（x，y）在S中
如果x和y在s中，则lcd（x，y）在s中
附加约束：数组a的大小为a中的每个x≤50000、k≤1012和x≤1012。程序必须在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英寸
GCD（10，15）=5英寸
GCD（12，15）=3英寸
LCM（10，12）=60英寸
…
最后：
s={1，2，3，5，10，12，15，30，60}
最佳答案
把k分解成不同素数的幂。对于每一个这样的素数功率因数，计算它是除数的所有数组元素的gcd。如果（且仅当）某个gcd不是k的除数，则s不包含k。
正确性证明涉及正整数是带有算子GCD和LCM的分配格这一事实。
关于algorithm - 算法-GCD和LCM问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34471157/