Diophantine reciprocals I
题号:108 难度: 30
中英对照
In the following equation x, y, and n are positive integers.
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