c++ - 我怎样才能知道是否可以使用它使数组中的数字相等？

Question

这个问题是在面试中问到我的，我真的想不出一个解决方案:

如果给我一个包含一些数字的数组，我可以将每个数字无限次地翻倍或翻三倍，我只需要找出这些数字是否可以彼此相等，如何我可以做吗？这可能是什么算法？

Answer 1

让我们从该数组中取出两个元素，并将它们命名为a 和b。现在让我们将它们加倍和加倍，直到它们相等:

a * 2^i * 3^j == b * 2^m * 3^n

由此我们可以得出结论，如果(通过上述等式的简单变换)，这是可行的

a / (2^m * 3^n) == b / (2^i * 3^j)

起初，这似乎没什么用。但请记住，每个数字都可以表示为其质因数的乘积:

c = 2^u * 3^v * 5^w * 7^x * 11^y * ...
(u, v, w, ... may be 0)

现在将其应用于前面的等式，如果我们使 m 和 n 等于 2 和 3 的数量(u 和 v) a 的所有剩余部分将是除 2 和 3 之外的所有质因数的乘积。对 b 做同样的事情，然后比较结果。

现在将其放入算法(并将其应用于更多数字)并不是那么困难(尽管我们需要小心，因为我们肯定不想计算所有元素的所有质因数)。

1. 取第一个元素
2. 除以 2 直到不能再被 2 整除
3. 相同，但用于 3
4. 将其保存为要比较的值
5. 取下一个元素
6. 除以2，只要它能被2整除
7. 同样适用于 3
8. 将结果与保存的值进行比较，如果不同则返回false
9. 否则，如果还有剩余元素，则转到 5。
10. 如果没有剩余元素，返回true