计算具有相同结果的给定取幂对的不同项

Question

要理解这个问题,让我们先考虑这些例子:

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

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

                                 27 ³ = 3 ⁹ = 19683

所以,27 ³和3 ⁹都是相同的.

现在的问题是,对于任何给定对一个^b如何计算可能的所有其他(如果有的话)X ^Ý其中,一个^b = X ^ý .I很感兴趣的,可以在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 期望的输出: No duplicate possible

Answer 1

这主要是一个数学问题.你可以提取一个数字的所有素数因子,你将得到素数及其指数的列表,即216000 = 2 ⁶*3 ³*5 ³.然后取指数的GCD:GCD(6,3,3)= 3.用GCD除以指数得到数字的最小根,2 ²*3 ¹*5 ¹ = 60.然后考虑GCD -因子3是1和3.有一种方法可以将数字表示为GCD每个因子的积分幂.您可以将其表达为(60 ³)¹或(60 ¹)³.

编辑:修复数学错误.