algorithm - 寻找满足等式 1/x + 1/y = 1/n 且 x、y 和 n 为整数的不同对 {x, y}

Question

任务是找到满足方程 1/x + 1/y = 1/n 的不同对 {x, y} 的数量，其中 n 是用户给出的输入。 x 和 y 的不同顺序不算作新对。

例如，值 n = 2 将表示 1/n = 1/2。 1/2可以由两对{x, y}组成，分别是6和3和4和4。

值 n = 3 表示 1/n = 1/3。 1/3可以由两对{x, y}组成，分别是4和12和6和6。

1/x + 1/y = 1/n 的数学方程可以转换为 y = nx/(x-n) 其中如果 y和x在转换后的等式中是一个整数，它们算作一对{x，y}。使用上述转换后的公式，我将从 x = n + 1 开始迭代 n 次，每次迭代将 x 加 1 以查找是否 nx % (x - n) == 0;如果结果为真，则 x 和 y 是一对新的不同的对。

通过手动计算答案并找到重复“模式”的次数，我找到了将迭代限制为 n 次的答案。 x 也以 n+1 开头，否则会被零除，或者 y 会得到负数。取模运算符是为了表示得到的y是整数。

问题:

• 为什么迭代被限制在 n 次背后有数学解释吗？通过手动计算并找到模式，我发现迭代的限制是 n 次:我只需要迭代 n 次即可找到不同对的数量。
• 除了我上面的方法，还有另一种方法可以找到不同对 {x, y} 的数量，即找到不同对本身的值，然后对不同对的数量求和吗？有没有我不知道的快速数学公式？

作为引用，我的代码可以在这里看到:https://gist.github.com/TakeNoteIAmHere/596eaa2ccf5815fe9bbc20172dce7a63

Answer 1

假设 x,y,n > 0 我们有

观察 1:x 和 y 都必须大于 n

观察 2:由于 (x,y) 和 (y,x) 不算作不同，我们可以假设 x <= y。

观察 3:x = y = 2n 总是一个解，如果 x > 2n 则 y < x(因此没有新解)

这意味着 x 的可能值是从 n+1 到 2n。