7

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

也就是说，给定一个数字 n，我想找到 b(base) 和e(exponent) 这样

n = b e

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

Ps: n bande都是正整数。

4

4 回答 4

7

首先找到 的素数分解n：n = p1e1 p2e2 p3e3 ...

然后用欧几里得算法g求, , , ... 的最大公约数。e1e2e3

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

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

你有。n = be

于 2011-12-26T11:12:27.090 回答
4

我认为蛮力方法应该有效：尝试e从 2 开始的所有 s （1 是一个简单的解决方案），然后向上，采取r = n ^ 1/e， a double。如果r小于 2，则停止。否则，计算ceil(r)^eandfloor(r)^e并将它们与n（您需要ceilandfloor以补偿浮点表示中的错误）进行比较。假设您的整数适合 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
于 2011-12-26T11:19:14.597 回答
3

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

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

于 2011-12-26T11:11:39.820 回答
2

混合 interjay 和 dasblinkenlight 的方法。首先在 的素因数分解中找到所有小的素因数（如果有的话）及其指数n。'small' 的适当值取决于n，对于 mediumsized n，p <= 100可能足够，对于large n，p <= 10000或者p <= 10^6可能更合适。如果你找到任何小的素因数，你就知道它e必须除以你找到的所有指数的最大公约数。很多时候，这gcd将是 1。无论如何，可能的指数范围将会缩小，如果n没有小的素因数，你知道e <= log(n)/log(small_limit)，这是一个很好的减少log(n)/log(2)，如果你找到了几个小的素因数gcd，他们的指数是g，而剩下的辅因子n是m，只需要勾选g不超过的除数即可log(m)/log(small_limit)。

于 2011-12-26T17:04:48.967 回答