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

Question

最快的方法是什么？

我的简单方法:

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的答案,因为它应该更好(除了它的实现有点复杂,我还没有测试过).

Answer 1

第 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 发布的 20 个具有 15 位数字的示例总共需要 0.03 秒，这已经至少加速了 1000 倍。更复杂的实现应该会带来更大的改进。

相比之下，Egor Skriptunoff 提出的 O(A^(1/3)) 方法的快速而肮脏的 Python 实现对于同一列表需要 0.7 秒。对于易于实现的方法来说，这当然是一个好的结果。