以幂形式表示的整数

Question

如果存在某个 a > 0 和某个 x > 1，使得 N = a^x，则称数字 N 可以表示为幂形式。

现在我们可以取对数，方程变成 log(n)/log(a)=x，所以通过从 (2,sqrt(n)) 迭代，如果存在任何一个数字可以给出整数 x，那么该数字的 x 次方就可以表示为 N。

下面是检查相同问题的代码：

from math import log,sqrt,floor
n=int(input())
t=floor(sqrt(n))+1
flag=False


for i in range(2,t):
    x=log(n)/log(i)
    if x==int(x):
        print("YESSSSSSSSSSSSS!")
        flag=True
        break

if not flag:
    print("Nooooooooooooooooooo!")

时间复杂度：O(n)

这个问题还有其他替代/更好的解决方案吗？

- Demonking28

---

这是一个数学还是编程问题？ - Klaus D.

抱歉，这个问题最好在我们的数学相关的姊妹网站上提出。 - Klaus D.

时间复杂度并不是你在这里的主要问题，浮点数精度才是。尝试使用 n = 76 ** 89 - 1 和 n = 76 ** 89。 - Mr. T

即使在小数中，浮点数精度也会失败 log(1<<29) / log(2) != 29。您可能需要使用 x - int(x) < ESP 比较来替代 ==。 - Blownhither Ma

不错的观点 @BlownhitherMa 即使是 3 ** 5 也失败了。 - Mr. T

Answer 1

更好的方法是采用以下算法：

x <- 0
i <- 2
found <- false
do
    x <- root(N, i)
    if (x is integer) then
       found <- true
    end if
    i <- i + 1
while (x >= 2) and (not found)

这个算法比线性算法更快。我认为它是对数级别的，但没有时间去检查。

- Lajos Arpad

---

当 i 为 2 时，root(N,i) 是平方根，当 i 为 3 时，是立方根，以此类推。 - Lajos Arpad

它是对数级别的，因为它会在i达到N的以二为底的对数之前停止或停止。 （如果i是N的以二为底的对数，则root（N，i）为2。） - Eric Postpischil

@LajosArpad 谢谢，这正是我在寻找的 :) - Demonking28

@Demonking28，不用谢。如果我的答案解决了您的问题，那么您可以考虑将其接受为正确的解决方案。 - Lajos Arpad