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