玩阵列游戏

Question

Hi无法找到以下问题的解决方案(这里有一个指向原始问题：Sumita and equal array 的链接)。请帮帮忙？

Sumita正在玩一个大小为N的数组A，她想使A的所有值都相等。她可以将数组中任意数量的值乘以X、Y和Z。你的任务是告诉她她是否能做到。打印“她可以”--如果她能做到--再打印“她不能”--“没有”

投入：

First line of the input will contain T (No. of test cases).
For each test case, first line will contain four space separated integers denoting N, X, Y and Z.
Then next line will contain N space separated integers of A

产出：

For every test case, print the required answer in a new line.

制约因素：

1 ≤ T ≤ 5
2 ≤ N ≤ 10^5
X, Y, Z ∈ {2, 3, 5, 7}
1 ≤ Ai ≤ 10^9

样本输入：

2
2 2 2 2
2 4
3 2 3 2
2 6 7

样本输出：

She can
She can't

解释：

Test case #1: Multiply first value by 2.
Test case #2: Not possible.

到目前为止我的工作：我找到了X，Y，Z的lcm，如果这个数组中的每个元素被lcm除以或者可以被lcm除以，那她就不能了

Answer 1

既然你给出了你自己的想法，但没有代码，我也会这样做:给一些想法，但没有代码。如果你试图对这个想法进行编码，然后陷入困境，通过展示你的代码来编辑你的问题，并寻求更多的帮助。

找到给定数组中的数字的最小公共倍数(LCM)的想法是正确的。对于数组中的每个元素，您可以计算LCM和元素的商--这个商保证是一个正整数。然后看看这个商是否有素除数，不是X，Y或者Z。如果有这样的除数，那么你的任务是不可能的：“她不能”。如果没有这样的除数，那么这个元素就通过了测试。如果所有元素都通过了此测试，则任务是可能的：“她可以”。

对于第一个数组[2, 4]和X, Y, Z值[2, 2, 2]，数组的LCM是4。第一个商是4 // 2 = 2，这个商的唯一素数因子是2，它在X, Y, Z的列表中。第二个商是4 // 4 = 1，它没有素数除数，因此该元素也通过了测试。所有元素都通过了测试。所以任务是有可能的。

对于第二个数组[2, 6, 7]和X, Y, Z值[2, 3, 2]，数组的LCM是42。第一个商数是42 // 2 = 21，它有质数因子3和7。第一个(3)在X, Y, Z列表中，但最后一个(7)不是，所以任务是不可能的。不需要检查数组中其他元素的商。

你能编个程序吗？注意，我使用的是Python的列表，而不是数组。还要注意的是，这个算法取决于质数X, Y, Z的可能值--如果它们可以是复合数，则算法需要调整，而且会更复杂。更准确地说，如果X, Y, Z的任何两个可能的值都是不同的，并且不是相对素数(最大的公共除数大于一个)，则需要更改算法。