ZOJ Problem Set - 1856
You have a drawer that is full of two kinds of socks: red and black. You know that there are at least 2 socks, and not more than 50000. However, you do not know how many there actually are, nor do you know how many are red, or how many are black. (Your mother does the laundry!)
You have noticed, though, that when you reach into the drawer each morning and choose two socks to wear (in pitch darkness, so you cannot distinguish red from black), the probability that you pick two red socks is exactly p/q, where 0 < q and 0 <= p <= q.
From this, can you determine how many socks of each colour are in your drawer? There may be multiple solutions - if so, pick the solution with the fewest total number of socks.
Input is terminated by a line consisting of two zeroes.
Source: University of Waterloo Local Contest 1999.06.19