7

それを行う最も速い方法は何ですか？

私の簡単なアプローチ：

for (C = 1;C<sqrt(A);C++) {
 B=A/(C*(C+1));
 if B is natural then add B,C to the list of possible pairs. 
}

O（sqrt（A））未満で実行できますか？

解決

Egor Skriptunoff が回答したように、O(cube_root(A)) で簡単に実行できます。

これは単純な JavaScript の実装です。

function findBCs(A) {
    if (A / 2 != Math.floor(A / 2)) return [];
    var solution = [];
    var i;
    var SR3 = Math.pow(A, 1 / 3);
    for (i = 1; i <= SR3; i++) {
        var B, C;
        C = i;
        B = A / (C * (C + 1));
        if (B == Math.floor(B)) {
            solution.push([B, C]);
        }

        B = i;
        C = (-1 + Math.sqrt(1 + 4 * A / B)) / 2;
        if (C == Math.floor(C)) {
            solution.push([B, C]);
        }
    }

    return solution;
}

それはより良いはずなので、私はMehの答えを受け入れます（その実装はもう少し複雑で、私はテストしていません）。

4

3 に答える 3

4

O(cube_root(A))
これはIndeed で行うことができB、あなたの数字の 1 つCです。cube_root(A)

于 2013-08-17T08:17:03.990 に答える
4

ステップ 1: 因子 A

ステップ 2: A の素因数からすべての約数の集合 S を見つけます。

ステップ 3: S の各除数 c について、c+1 が A も除算するかどうかを確認します。そうであれば、b=A/(c*(c+1)) は解です。(これは、c と c+1 が互いに素であることを使用します。したがって、c と c+1 の両方が A を割り切る場合、c*(c+1) も割り切れます)。

これの複雑さは、要因 AEg に使用される方法に依存します。たとえば、Pollard-rho (これは比較的単純です) を実装する場合、実装の複雑さは最悪の場合で約 O(A^0.25) になります。そして、これはまだ最善の答えではありません。もちろん、より良い因数分解アルゴリズムがあります。また、入力が多くの除数を含む特殊なケースである場合、因数分解は簡単になり、除数の数が制限の問題になります。

もちろん、この方法の利点は、一般的に役立つ関数 (因数分解など) に時間を費やすことができることです。これにより、他の同様の問題を簡単に解決できます。Python での Pollard-rho の私自身の実装では、6502 によって投稿された 15 桁の 20 の例で合計 0.03 秒が必要ですが、これは少なくとも 1000 倍の速度向上です。より洗練された実装は、はるかに大きな改善につながるはずです。

比較のために、Egor Skriptunoff によって提案された O(A^(1/3)) メソッドの素早い Python 実装では、同じリストに 0.7 秒が必要です。これはもちろん、実装が容易な方法としては良い結果です。

于 2013-08-17T09:54:21.087 に答える