number-theory - xy+yz+ xz = N 的不同解数

Question

我一直在尝试解决 spoj 上的问题。
这是问题的链接。

http://www.spoj.pl/problems/TAP2012B/

根据我的解释，我需要找到方程 xy+yz+xz = N 的解数
其中 n 是给我们的。
x>=y>=z
z 可以为零。
但是 x 和 y 不能。
我尝试通过实现 3 个 for 循环来解决这个问题(不好的方法)。
它给出了正确的答案，但它太慢了。
此外，其他人几乎很快就解决了(0.00)
所以我相信有一个非常不同的方法来解决这个问题。
对于 N = 20，
不同解决方案的数量是 5 :
(6,2,1)
(5,4,0)
(10,2,0)
(4,2,2,)
(20,1,0)

Answer 1

也许有一些基于数论的绝妙解决方案。但简单地重新思考任务也可以降低算法的复杂性。

例如，我们不需要第三个循环，因为我们可以计算 z如 (N - x*y)/(x+y) .我们不必运行 y一路到x正如我们所知，每次z不是负数，因此 N >= xy .

N = 9747
for x in range(1, N+1):
    max_y = min( N / x, x) 
    for y in range(1, max_y+1):
        if (N - x*y) % (x+y) == 0:
            z = (N - x*y) / (x+y)
            if z <= y:
                print x,y,z