如何检查给定数字是否为x ^ y形式？

Question

我正在准备我的采访并遇到了这个问题:

编写程序以检查数字n是否为x ^ y形式.已知n,x和y是整数,x和y大于2.

我想过采取日志和东西,但无法弄清楚如何检查数字是否是形式.你能帮忙吗？:)

Answer 1

"采取日志和东西"是要走的路.注意,对于整数a,n> 1绝不是a ^ b,b> log_2(N).因此,对于2和log_2(N)之间的每个整数b,您可以检查楼层(N ^(1/b))^ b = N. 你必须做log(N)许多指数,每个指数产生一个最大N的数.

这比@ dasblinkenlight的解决方案要快得多,这需要您首先考虑N. (没有多项式时间算法---也就是说,N中的位数多项式对于整数因子分解是已知的.但是,可以在多项式时间内使用小指数进行整数求幂.)

Answer 2

解决这个问题的一种方法是分解n,计算各个因素,并找出计数的最大公分母.如果GCD为1,则答案为"否".否则,答案是"是".

这里有些例子:

• 7,素因子7(一次).我们有一个因素重复一次.回答"否",因为GCD是1.
• 8,素因子2(3次).我们有一个因子,数量为三.回答"是",因为GCD是3.
• 144,素因子2(4次)3(2次).4和2的GCD是2,所以答案是"是".
• 72,素因子2(3次)3(2次).3和2的GCD是1,所以答案是"否".