如何检查一个数字是否可以表示为5的幂的和

Question

如何检查一个数字是否为5的幂？

我能想到以下算法。有没有改进它的方法？有没有数学技巧？

1.首先检查数字的最后一位是否为5。 2.如果最后一位是5，则将其除以5。 如果除法的结果是1，则该数字是5的幂。 否则，检查除法结果本身是否是5的幂（即用结果作为数字回到步骤1）。

- Kaushik Lele

---

看这个：http://math.stackexchange.com/questions/22580/how-to-check-if-a-integer-is-a-power-of-some-integer - Edouard Thiel

@mat，你对于去掉步骤有什么建议？你说的“离题”是什么意思？如果你知道具体的文档，请指出来。这比发表这样的评论更有帮助。 - Kaushik Lele

有什么数学技巧吗？ 你的算法似乎是有效的，除非你想用汇编语言编码并需要进行优化。 输入可以有多大？可以是成千上万位的数字，以文本文件形式发送吗？ - Timothy Ha

@TimothyHa 数字可能非常大或非常小。我更倾向于知道比我的近乎原始的方法更好的解决方案。 - Kaushik Lele

如果数字有成千上万位，不适合INT或LONG（如Pham Trung的答案中所述），则您的算法将无法工作。而且取对数可能也会成为一个问题。 - Timothy Ha

Answer 1

你不需要查看每个数字，你可以这样做：

n = (int)(log(x) / log(5)); // get n = log5(x), truncated to integer
if (pow(5, n) == x)         // test to see whether x == 5^n
    // x is a power of 5

在线演示

- Paul R

---

听起来不错。但从编程/算法的角度来看，“log”方法可能并不在每种语言中都可用。 - Kaushik Lele

真实 - 我不知道有任何现代语言不具备基本的数学函数，例如log、pow等，但你永远不知道。当然，如果语言不支持它们，您始终可以实现自己的版本。 - Paul R

Answer 2

只有很少的五次方数适合int/long范围，因此您只需要生成所有这些数字并一一检查（不到60个数字），使用HashSet将具有O（1）时间复杂度

- Pham Trung

---

我的计算机科学教授过去常常给我大文件中的数字，而不是使用int或long类型。 - Timothy Ha

@TimothyHa 在 HashSet 中，您可以保存字符串、BigNums 或任何表示形式（如哈希、模算术等）。但是，您可以在 O(lg n) 的时间内轻松检查它，而无需存储结果。请查看我的答案。Pham Trung：+1，因为写了关于 O(1) 解决方案（预处理后）。 - Tacet

Answer 3

连续除以5直到得到不能再被5整除的数字，并检查结果是否等于1，这是一个不错的解决方案。它需要log_5(n)个操作，因此时间复杂度为O(lg n)，非常快速。例如对于9094947017729282379150390625，只需要40次操作！

- Tacet

---

在这个运行时中，n是什么？ - Hengameh

这是要检查的数字。（假设除以5的复杂度为O(1)。显然对于数位数百万的数字而言是错误的，但任何算法都会面临这个问题，所以我跳过了这一步。）包括数字的大小在内，它将接近于O(lg^2 n)。 - Tacet

Answer 4

我会先创建一个5的幂次方数字数组。你可以使用一个范围，然后对于范围内的每个值，将该值提高到五次方，并将新值推入数组中。

然后，你可以查找数字n是否包含在数组中。

- Darkmouse