当前位置：首页 » Project Euler » 详细页

Diophantine reciprocals I 题号：108 难度： 30 中英对照

In the following equation x, y, and n are positive integers.

1
x
 +
1
y
 =
1
n

For n = 4 there are exactly three distinct solutions:

1
5
 +
1
20
 =
1
4
1
6
 +
1
12
 =
1
4
1
8
 +
1
8
 =
1
4

What is the least value of n for which the number of distinct solutions exceeds one-thousand?

NOTE: This problem is an easier version of Problem 110; it is strongly advised that you solve this one first.

Solution

原方程为 $$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$$ 因此$x>n,y>n$，令$x=n+r,y=n+s$，则有 $$\frac{1}{n+r}+\frac{1}{n+s}=\frac{1}{n}$$ 化简： $$\frac{n+s+n+r}{(n+r)(n+s)}=\frac{1}{n}$$ $$n(n+s+n+r)=(n+r)(n+s)$$ $$n^2=sr$$ 所以$s,r$均是$n^2$的因子，也就是说$n^2$所有的因子对都是解。 假设$d(n^2)$为$n^2$的因子数，由于$n$是$n^2$的一个因子，则$d(n^2)$一定是一个奇数，原问题就转化为求最小的n满足 $$\frac{d(n^2)+1}{2}>1000$$ 把$N^2$写成素数乘积的形式： $$N^2=(p_1^{a_1}p_2^{a_2}...p_n^{a_n})^2=p_1^{2a_1}p_2^{2a_2}...p_n^{2a_n}$$ 利用乘法原理可求得$N^2$的因子个数为 $$d(N^2)=(2a_1+1)(2a_2+1)...(2a_n+1)$$

Code 

using System;
class p108
{
    public static void Main(string[] args)
    {
        var start = DateTime.Now;
        var result = Run();
        var end = DateTime.Now;
        Console.WriteLine(result);
        Console.WriteLine("Solution took {0} ms", (end - start).TotalMilliseconds);
        Console.Read();
    }
    public static String Run()
    {
        for (int n = 1; ; n++)
        {
            if ((countDivisorsSquared(n) + 1) / 2 > 1000)
                return n.ToString();
        }
    }
    // Returns the number of divisors of n^2
    private static int countDivisorsSquared(int n)
    {
        int count = 1;
        for (int i = 2, end = Convert.ToInt32(Math.Sqrt(n)); i <= end; i++)
        {
            if (n % i == 0)
            {
                int j = 0;
                do
                {
                    n /= i;
                    j++;
                } while (n % i == 0);
                count *= j * 2 + 1;
                end = Convert.ToInt32(Math.Sqrt(n));
            }
        }
        if (n != 1)  // Remaining largest prime factor
            count *= 3;
        return count;
    }
}
180180
Solution took 165.512 ms

public final class p108  {
    public static void main(String[] args) {
        long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    public static long run() {
        for (int n = 1; ; n++) {
            if ((countDivisorsSquared(n) + 1) / 2 > 1000)
                return n;
        }
    }
    // Returns the number of divisors of n^2
    private static int countDivisorsSquared(int n) {
        int count = 1;
        for (int i = 2, end = (int) Math.sqrt(n); i <= end; i++) {
            if (n % i == 0) {
                int j = 0;
                do {
                    n /= i;
                    j++;
                } while (n % i == 0);
                count *= j * 2 + 1;
                end = (int) Math.sqrt(n);
            }
        }
        if (n != 1)  // Remaining largest prime factor
            count *= 3;
        return count;
    }	
}
180180
95ms