math - 查找大整数是否是十的幂的最快方法是什么？

Question

我可以在循环中使用除法和模数，但这对于非常大的整数来说很慢。该数字以 2 为基数存储，可能大到 2^8192。我只需要知道它是否是十的幂，所以我认为可能有一个快捷方式(除了使用查找表)。

Answer 1

如果你的数字 x 是十的幂，那么

x = 10^y

对于某个整数 y，这意味着

x = (2^y)(5^y)

因此，将整数右移直到没有更多的尾随零(应该是一个成本非常低的操作)并计算移位的位数(称为 k)。现在检查剩余的数字是否为 5^k。如果是，那么您的原始数字是 10 的幂。否则，不是。由于 2 和 5 都是素数，因此这将始终有效。