c++ - 计算具有相同结果的给定对幂的不同项

Question

为了理解这个问题，让我们首先考虑这些例子:

4⁶ = (2²)⁶ = 2¹² = (2³)⁴ = 8⁴ = 16³ = 4096。

因此，我们可以说 4⁶,2¹²,8⁴ 和 16³ 相同。

27³ = 3⁹ = 19683

因此，27³ 和 3⁹ 是相同的。

现在的问题是，对于任何给定的 a^b 对，如何计算所有其他可能的(如果有的话)x^y 其中，a^b = x^y。我对一个算法感兴趣可以在 C/C++ 中高效地实现。

例如:

如果输入是这样的:

4,6 所需的输出:(2,12),(8,4)

8,4 所需的输出:(2,12),(2,6)

27,3 所需的输出:(3,9)

12,6 所需输出:(144,3),(1728,2)

7,5 所需输出:不可能重复

Answer 1

这主要是一道数学题。您可以提取一个数的所有质因数，然后您将得到一个质数及其指数列表，即 216000 = 2⁶ * 3³ * 5 ³。然后取指数的 GCD:GCD(6,3,3) = 3。将指数除以 GCD 得到数字的最小根，2² * 3¹ * 5¹ = 60。然后因式分解 GCD — 3 的因数为 1 和 3。有一种方法可以将数字表示为 GCD 的每个因数的整数幂。您可以将其表示为 (60³)¹ 或 (60¹)³。

编辑:修复了数学错误。