当前位置:首页 » 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