algorithm - 给定自然数A，我想找到所有自然数对(B，C)，以便B * C *(C + 1)= A

最快的方法是什么？
我简单的建议：

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的答案，因为它应该更好（此外，它的实现稍微复杂一些，我还没有测试）。

最佳答案

步骤1：因子A
第二步：从a的素因子中求出所有因子的集合。
第三步：对于S中的每个除数C，检查C+1是否也除数A。如果是，那么b=a/（c*（c+1））是一个解。（这使用c和c+1是互质的。因此，如果C和C+1都除以A，那么C*（C+1）也是如此。
这一点的复杂性取决于用于因子A的方法。例如，如果你实现例如Pollard rho（这是相对简单的），那么在最坏的情况下，实现的复杂性大约是O（a^ 0.25）。但这仍然不是最好的答案。当然有更好的分解算法。另外，如果你的输入是一个有很多因子的特殊情况，那么因子分解可能很容易，因子的数量是限制问题。
这种方法的优点当然是，你将花时间在一个通常有用的函数上（即因子分解），这将简化解决其他类似问题。我自己在python中实现的pollard rho需要总共0.03s来处理6502发布的15位数字的20个示例，这至少已经是1000倍的加速了。更复杂的实现应该会带来更大的改进。
相比之下，egor skriptunoff提出的o（a^（1/3））方法的一个快速而脏的python实现需要0.7s来实现相同的列表。对于一个易于实现的方法来说，这当然是一个很好的结果。