求整数幂根

Question

查找数字的所有整数幂根的最佳（最有效）算法是什么？

也就是说，给定一个数字 n，我想找到 b（基数）和e< /code> （指数）使得

n = b^e

我想获取b和e所有可能的值对

Ps: n b 和 e 为正整数。

Answer 1

首先求n的质因数分解：n = p1e1 p2 e2 p3e3 ...

然后求最大公约数g e1、e2、e3 ，...通过使用欧几里得算法。

现在，对于 g 的任何因子 e，您可以使用：

b = p1e1/e p2e2/e p3e3/e ...

你有n = be。

Answer 2

我认为蛮力方法应该有效：尝试从 2（1 是一个简单的解决方案）开始的所有 e，采用 r = n ^ 1/e，一个 双。如果r小于2，则停止。否则，计算 ceil(r)^e 和 floor(r)^e，并将它们与 n 进行比较（您需要 ceil 和 floor 来补偿浮点表示中的错误）。假设您的整数适合 64 位，则无需尝试超过 64 个的 e 值。

下面是一个 C++ 示例：

#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
typedef long long i64;
using namespace std;
int main(int argc, const char* argv[]) {
    if (argc == 0) return 0;
    stringstream ss(argv[1]);
    i64 n;
    ss >> n;
    cout << n << ", " << 1 << endl;
    for (int e = 2 ; ; e++) {
        double r = pow(n, 1.0 / e);
        if (r < 1.9) break;
        i64 c = ceil(r);
        i64 f = floor(r);
        i64 p1 = 1, p2 = 1;
        for (int i = 0 ; i != e ; i++, p1 *= c, p2 *= f);
        if (p1 == n) {
            cout << c << ", " << e << endl;
        } else if (p2 == n) {
            cout << f << ", " << e << endl;
        }
    }
    return 0;
}

当使用 65536 调用时，它会产生以下输出：

65536, 1
256, 2
16, 4
4, 8
2, 16

Answer 3

混合 interjay 和 dasblinkenlight 的方法。首先找出n 素因数分解中的所有小素因数（如果有）及其指数。 “small”的适当值取决于 n，对于中等大小的 n，p <= 100 就足够了，对于 Large n、p <= 10000 或 p <= 10^6 可能更合适。如果您找到任何小的质因数，您就知道e必须除以您找到的所有指数的最大公约数。通常，gcd 将为 1。无论如何，可能的指数范围将会减小，如果 n 没有小的质因数，您就知道 e e < ;= log(n)/log(small_limit)，这是对 log(n)/log(2) 的一个很好的缩减，如果您找到了几个小的质因数，他们的gcd指数为g，n的余数为m，只需检查g的除数即可不超过log(m)/log(small_limit)。

Answer 4

我的方法是否适合您的需求取决于任务的规模。

首先，有一个明显的解决方案：e = 1，对吧？
从那时起，如果你想找到所有的解决方案：我能想到的所有算法都需要找到 n 的某个素因数。如果这只是一个独立的任务，那么没有什么比对素数进行暴力破解更好的了（如果我没记错的话）。找到第一个质因数 p 及其相应的指数（即满足 p^k / n 的最大数字 k）后，您只需检查 e 的 k 的约数。对于每个这样的指数 l （再次 l 迭代 k 的所有除数），您可以使用二分搜索来查看 n 的 l 次方根是否为整数（相当于找到新的解决方案）。