求出 1/X + 1/Y=1/N 的可能解数，给出 N

Question

方程式为：1/X + 1/Y = 1/N

其中 X、Y 和 N 为正整数。

我必须找到可能的解决方案的数量，即 X 和 Y 对的值，因为 N 是已知的，因此可以解决上述方程。

很明显，对于任何解决方案 X > N 和 Y > N。所以我可以假设 X= N + a 和 Y= n + b。

所以方程简化为 1/(N+a) + 1/(N+b) =1/N 如果我们求解它，它简化为 N^2=ab。可以写成当

1. 当 a=1 b=N^2
2. 当 a=2 b=N^2/2 等等。

所以 a 的值将在 [1,N] 的范围内，b 的值将在 [N^2,N] 的范围内。但 X 和 Y 是正整数。因此 a 和 b 也是整数。

所以我必须对那些都是整数的 a 和 b 值对。

尝试给出一种算法方法。是的，尝试给出解决此类方程的优化方法。

Answer 1

以下是一些观察结果：

• 1/X+1/Y=1/N 相当于 (X-N)(Y-N)=N^2
• 如果 的质因数分解N是N = p1^i1*p2^i2*...*pk^ik那么答案是(2*i1+1)(2*i2+1)...(2*ik+1)（您可以使用公式推导出来）
• 你可以计算这个 O(sqrt(N)*log(N))

以下是进行因式分解 (Java) 的方法：

package stackoverflow;

import java.util.ArrayList;
import java.util.List;

public class Factorization {

    public static class Pair {
        long x, y;
        public Pair(long x, long y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return String.format("[%d, %d]", x, y);
        }
    }

    public static List<Pair> factorize(long n) {
        List<Pair> ans = new ArrayList<Pair>();
        for (long i = 2; i * i <= n; ++i) {
            int t = 0;
            while (n % i == 0) {
                n /= i;
                t++;
            }
            if (t > 0)
                ans.add(new Pair(i, t));
        }
        if (n > 1)
            ans.add(new Pair(n, 1));
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(factorize(24)); // [[2, 3], [3, 1]]
    }
}