UVa 10976

10976 - Fractions Again?!

• http://acm.uva.es/p/v109/10976.html

Summary

Given a value of k, find all positive integer solutions $[x,y]~(x\geq y$) of the equation $\frac{1}{k}=\frac{1}{x}+\frac{1}{y}$.

Explanation

Any valid value of y lies between k+1 and 2k, inclusive. We can loop over all possible values for y, and each time check whether the corresponding x is an integer.

Note that we first have to output the number of solutions. Thus we have to store all found solutions in a temporary array and output them only after we found all of them.

Gotcha

A solution that tries all possible values for x (from 2k to k*k+k) and calculates y is too slow and will timeout on large inputs.

Input

2
12
8999
10000

Output

2
1/2 = 1/6 + 1/3
1/2 = 1/4 + 1/4
8
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
2
1/8999 = 1/80991000 + 1/9000
1/8999 = 1/17998 + 1/17998
41
1/10000 = 1/100010000 + 1/10001
1/10000 = 1/50010000 + 1/10002
1/10000 = 1/25010000 + 1/10004
1/10000 = 1/20010000 + 1/10005
1/10000 = 1/12510000 + 1/10008
1/10000 = 1/10010000 + 1/10010
1/10000 = 1/6260000 + 1/10016
1/10000 = 1/5010000 + 1/10020
1/10000 = 1/4010000 + 1/10025
1/10000 = 1/3135000 + 1/10032
1/10000 = 1/2510000 + 1/10040
1/10000 = 1/2010000 + 1/10050
1/10000 = 1/1572500 + 1/10064
1/10000 = 1/1260000 + 1/10080
1/10000 = 1/1010000 + 1/10100
1/10000 = 1/810000 + 1/10125
1/10000 = 1/791250 + 1/10128
1/10000 = 1/635000 + 1/10160
1/10000 = 1/510000 + 1/10200
1/10000 = 1/410000 + 1/10250
1/10000 = 1/400625 + 1/10256
1/10000 = 1/322500 + 1/10320
1/10000 = 1/260000 + 1/10400
1/10000 = 1/210000 + 1/10500
1/10000 = 1/170000 + 1/10625
1/10000 = 1/166250 + 1/10640
1/10000 = 1/135000 + 1/10800
1/10000 = 1/110000 + 1/11000
1/10000 = 1/90000 + 1/11250
1/10000 = 1/88125 + 1/11280
1/10000 = 1/72500 + 1/11600
1/10000 = 1/60000 + 1/12000
1/10000 = 1/50000 + 1/12500
1/10000 = 1/42000 + 1/13125
1/10000 = 1/41250 + 1/13200
1/10000 = 1/35000 + 1/14000
1/10000 = 1/30000 + 1/15000
1/10000 = 1/26000 + 1/16250
1/10000 = 1/25625 + 1/16400
1/10000 = 1/22500 + 1/18000
1/10000 = 1/20000 + 1/20000