Project Euler 110

In the following equation xy, and n are positive integers.
1
x
+
1
y
=
1
n
It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.
What is the least value of n for which the number of distinct solutions exceeds four million?


My solution~!

1/x + 1/y = 1/n
n/x + n/y = 1
n + nx/y = x
ny + nx = xy
xy - ny -nx =0
xy -ny -nx + n^2 = n^2
(x-n)(y-n) = n^2

if I change x-n = A
               y-n = B

AB = n^2
A and B is divisor of n^2
so we can calculate count of divisors of n^2.

just find n that divisorCount/2 exceeds four million.






Comments

Popular posts from this blog

Project euler 169 found clue

Floyd-Warshall's algorithm