什么是做到这一点的最快方法？

What's the fastest way to do it?

我的简单的形式给出：

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（开方（A））？

Can it be done in less than O(sqrt(A))?

解决方案

作为叶戈尔Skriptunoff答案，可以很容易地为O完成（cube_root（A））。

As Egor Skriptunoff answers, it can be done easily in O(cube_root(A)).

下面是一个简单的JavaScript实现。

Here is a simple javascript implementation.

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;
}

我接受咩的答案，因为它应该会更好（除了它的实现是一个有点复杂，我还没有测试过）。

I accept Meh's answer because it should be better (besides it's implementation is a little more complex and I have not tested).

推荐答案

步骤1：系数A

第2步：从A的主要因素，找到所有约数的集合S

Step 2: Find the set S of all divisors from the prime factors of A.

第三步：对于每一个因子c在S，检查C + 1把一个了。如果是的话那么B = A /（C *（C + 1））是一个解决方案。 （这将使用C和C + 1互质。因此，如果C和C + 1鸿沟的话也是如此C *（C + 1））。

Step 3: For each divisor c in S, check if c+1 divides A too. If it does then b=A/(c*(c+1)) is a solution. (This uses that c and c+1 are coprime. Thus if both c and c+1 divide A then so does c*(c+1)).

的这种复杂性取决于所使用的因子AEG的方法中，如果实现例如波拉德-rhO型（这是相对简单的），则实现的复杂性是约0（A ^ 0.25）在最坏的情况下。而这还不是最好的答案。当然也有较好的分解算法。也如果输入是一个特殊情况，有很多的除数，然后保可以很容易和除数的数是限制问题。

The complexity of this depends on the method that is used for factor A. E.g., if you implement for example Pollard-rho (which is relatively simple) then the complexity of the implementation is about O(A^0.25) in the worst case. And this still isn't the best possible answer. There are of course better factoring algorithm. Also if your input is a special case with lots of divisors, then factoring can be easy and the number of divisors is the limiting problem.

该方法的优点是当然，你会花时间在一个普遍有用的功能（即分解），这将简化解决其他类似问题的。我自己在Python实现波拉德-RHO的一共需要0.03 S为20例与15位发布的6502，这已经是一个因素1000更复杂的实现应导致更大的改进，至少加速。

The advantage of this method is of course that you'll spend your time on a generally useful function (i.e factorization), which will simplify solving other similar problems. My own implementation of Pollard-rho in Python needs a total of 0.03 s for the 20 examples with 15 digits posted by 6502, which is already at least a speedup of a factor 1000. More sophisticated implementations should lead to much larger improvements.

为了比较，一个快速和肮脏的Python实现的O（A ^（1/3））的方法提出了叶戈尔Skriptunoff都需要0.7秒的相同的列表。当然，这是一个很好的结果为一种方法，很容易实现。

For comparison, a quick and dirty Python implementation of the O(A^(1/3)) method proposed by Egor Skriptunoff needs 0.7s for the same list. This is of course a good result for a method that is easy to implement.