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

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

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

于 2013-08-17T09:54:21.087 回答
4

它可以在O(cube_root(A))
Indeed 中完成，您的数字之一B并且C必须小于cube_root(A)

于 2013-08-17T08:17:03.990 回答
-1

这条蟒蛇似乎工作：

from __future__ import division
from math import sqrt

def bcc1(a):
    ans = []
    if a % 2: return ans   # for odd a
    for b in range(1, a // 2 + 1):
        c = max(1, int(sqrt(a / b)))
        if b*c*(c+1) == a: 
            ans.append((b,c))
    return ans

for a in range(2, 51, 2):
    print('a: %2i -> (b, c): %r' % (a, bcc1(a)))

产生的输出是：

a:  2 -> (b, c): [(1, 1)]
a:  4 -> (b, c): [(2, 1)]
a:  6 -> (b, c): [(1, 2), (3, 1)]
a:  8 -> (b, c): [(4, 1)]
a: 10 -> (b, c): [(5, 1)]
a: 12 -> (b, c): [(1, 3), (2, 2), (6, 1)]
a: 14 -> (b, c): [(7, 1)]
a: 16 -> (b, c): [(8, 1)]
a: 18 -> (b, c): [(3, 2), (9, 1)]
a: 20 -> (b, c): [(1, 4), (10, 1)]
a: 22 -> (b, c): [(11, 1)]
a: 24 -> (b, c): [(2, 3), (4, 2), (12, 1)]
a: 26 -> (b, c): [(13, 1)]
a: 28 -> (b, c): [(14, 1)]
a: 30 -> (b, c): [(1, 5), (5, 2), (15, 1)]
a: 32 -> (b, c): [(16, 1)]
a: 34 -> (b, c): [(17, 1)]
a: 36 -> (b, c): [(3, 3), (6, 2), (18, 1)]
a: 38 -> (b, c): [(19, 1)]
a: 40 -> (b, c): [(2, 4), (20, 1)]
a: 42 -> (b, c): [(1, 6), (7, 2), (21, 1)]
a: 44 -> (b, c): [(22, 1)]
a: 46 -> (b, c): [(23, 1)]
a: 48 -> (b, c): [(4, 3), (8, 2), (24, 1)]
a: 50 -> (b, c): [(25, 1)]
于 2013-08-17T08:53:10.633 回答