How I solved the UVa 10976 - Fractions Again

Here's the problem link:  UVa 10976 - Fractions Again

Caution: This is a spoiler with complete solution. Do not read further if you haven't tried it yet.

Abbreviated problem definition: Given a fraction 1/z, it can be represented as 1/x + 1/y where x >=y. Find all combinations for a given 0 < z <= 10000.

Sample Inputs:

2

12

Sample Outputs:

2 --# of solutions

1/2 = 1/6 + 1/3

1/2 = 1/4 + 1/4

8 --# of solutions

1/12 = 1/156 + 1/13

1/12 = 1/84 + 1/14

1/12 = 1/60 + 1/15

1/12 = 1/48 + 1/16

1/12 = 1/36 + 1/18

1/12 = 1/30 + 1/20

1/12 = 1/28 + 1/21

1/12 = 1/24 + 1/24

Expression:

1/z = 1/x + 1/y

1/z = (y + x)/ (x * y)

z = (x * y)/(x + y) --(1)

z * (x + y) = (x * y)

z * x + z * y = y * x

z * y = (y - z) * x

x = (z * y) / (y - z) --(2)

Looking at the pattern for the samples, we decrease y and find the x,

if possible.

Start with y = 2 * z = 2 * 2 = 4:

1/2 = 1/4 + 1/4

2 = (4 * 4)/(4 + 4) --using (1)  above.

Try y = 3;

2 = (x * 3)/ (x + 3)

2 * (x + 3) = x * 3

2*x + 6 = 3*x

3*x - 2*x = 6

x = 6

So, one more solution found:

1/2 = 1/6 + 1/3

We cannot go further as y becomes equal to 2.

Full answers:

1/2 = 1/4 + 1/4

1/2 = 1/6 + 1/3

Let us look at the second sample:

Start with y = 12 * z = 12 * 2 = 14:

1/12 = 1/24 + 1/24 --Obvious :-)

Reduce y to 23:

Using (1) above we get:

12 = (x * 23)/(x + 23)

12 * (x + 23) = 23 * x

12*x + 276 = 23*x

276 = 11*x

x = 276/11 = 25.0909 => NOT a solution as we need 11 to exactly divide 276

Reduce y to 22:

Using (1) above we get:

12 = (x * 22)/(x + 22)

12*x + 12 * 22 = 22 * x

12 * 22 = 10 * x => NOT a solution

Reduce y to 21:

Using (1) above we get:

12 = (x * 21)/(x + 21)

12 * (x + 21) = 21 * x

12*x + 12 * 21 = 21*x

12 * 21 = 9*x 

x = 28 => We have a solution :-)

1/12 = 1/28 + 1/21

Reduce y to 20:

Using (1) above we get:

12 = (x * 20)/(x + 20)

12*x + 12*20 = 20*x

12*20 = 8*x

x = 30 => we have a solution :-)

1/12 = 1/30 + 1/20

Reduce y to 19:

Using (1) above we get:

12 = (x * 19)/(x + 19)

12*x + 12*19 = 19*x

12*19 = 7*x

x = 32.57 => NOT a solution

Reduce y to 18:

Using (1) above we get:

12 = (x * 18)/(x + 18)

12*x + 12*18 = 18*x

12*18 = 6*x

x = 36 => we have a solution :-)

1/12 = 1/36 + 1/18

Reduce y to 17:

Using (1) above we get:

12 = (x * 17)/(x + 17)

12*x + 12*17 = 17*x

12*17 = 5*x

x = 40.8 => NOT a solution

Reduce y to 16:

Using (1) above we get:

12 = (x * 16)/(x + 16)

12*x + 12*16 = 16*x

12*16 = 4*x

x = 48 => we have a solution :-)

1/12 = 1/48 + 1/16

Reduce y to 15:

Using (1) above we get:

12 = (x * 15)/(x + 15)

12*x + 12*15 = 15*x

12*15 = 3*x

x = 60 => we have a solution :-)

1/12 = 1/60 + 1/15

Reduce y to 14:

Using (1) above we get:

12 = (x * 14)/(x + 14)

12*x + 12*14 = 14*x

12*14 = 2*x

x = 84 => we have a solution :-)

1/12 = 1/84 + 1/14

Reduce y to 13:

Using (1) above we get:

12 = (x * 13)/(x + 13)

12*x + 12*13 = 13*x

12*13 = 1*x

x = 156 => we have a solution :-)

1/12 = 1/156 + 1/13

END when y = 12

There you go :-) 

There could be some optimization that can be performed for quickly

discarding some values of y. Will update.

We have used complete search to arrive at the solution.
One more spoiler: here's the source code