7

数値のすべての整数べき乗根を見つけるための最良の (最も効率的な) アルゴリズムは何ですか?

つまり、数値 が与えられた場合 、次のような(基数) と(指数) を見つけnたい be

n = be

bと のすべての可能な値のペアを取得したいe

Ps:n bとeは正の整数です。

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

ブルートフォースアプローチがうまくいくはずだと思います.2からすべてのsを試してください( e1は自明な解決策です) 。が 2 未満の場合は停止します。それ以外の場合は、 と を計算し、それらを比較します(浮動小数点表現のエラーを補正するためにとが必要です)。整数が 64 ビットに収まると仮定すると、 の 64 個を超える値を試す必要はありません。r = n ^ 1/edoublerceil(r)^efloor(r)^enceilfloore

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

私のアプローチがあなたのニーズに合うかどうかは、タスクの規模によって異なります。

まず、明らかな解が 1 つあります。e = 1 ですね。それ以降、すべての解を見つけたい場合: 私が考えることができるすべてのアルゴリズムは、n の素因数を見つける必要があります。これが単一の独立したタスクである場合、素数に対するブルートフォースよりも優れたものはありません（私が間違っていなければ）。最初の素因数 p とそれに対応する指数 (つまり、p^k / n となる最大の数 k) を見つけたら、k の約数だけ e をチェックする必要があります。そのような指数 l ごとに (ここでも l は k のすべての約数を反復します)、二分探索を使用して、n の l 乗根が整数であるかどうかを確認できます (新しい解を見つけることと同じです)。

于 2011-12-26T11:11:39.820 に答える
2

interjay と dasblinkenlight のアプローチをミックスします。まず、 の素因数分解ですべての小さな素因数 (存在する場合) とそれらの指数を見つけますn。'small' の適切な値は によって異なります。n中規模のn場合、大規模のp <= 100場合は十分であるか、より適切な場合があります。小さな素因数が見つかった場合は、見つけたすべての指数の最大公約数を割る必要があることがわかります。多くの場合、それは 1 になります。いずれにせよ、可能な指数の範囲は縮小されます。小さな素因数がない場合は、 からの適切な縮小であることがわかります。いくつかの小さな素因数が見つかった場合、それらの指数は np <= 10000p <= 10^6egcdne <= log(n)/log(small_limit)log(n)/log(2)gcdg、および の残りの余因子は でnあり、を超えないmことの除数のみを確認する必要があります。glog(m)/log(small_limit)

于 2011-12-26T17:04:48.967 に答える