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

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

 1x + 1y = 1n

For n = 4 there are exactly three distinct solutions:

 15 + 120 = 14 16 + 112 = 14 18 + 18 = 14

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.

### 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);
}
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
{
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