ZOJ Problem Set - 3266
DD and his girlfriend love a strange pingpong game. The rules are as follows:
1. If their points are not relative primes, they will reduce them to relatively prime. (If someone is 0 point, it is legal too.)
2. If someone reachs k points first after reduction, he/she will win the game.For example, a possible game can be:
1:1 -> 1:2 -> 1:1(2:2) -> 2:1 -> 3:1 -> 4:1 -> 2:1(4:2)
This problem contains MANY test cases(up to 350). You should process to the end of file.
For each case, the first line is a single integer k (1 <= k <= 1000) The second line contains two integers a b(0 <= a, b <= k), giving the score.
For each test case, you should only output one integer which indicates the minimum steps to get to the score. If it is impossible, output -1.
5 1 1 10 3 4
Author: WANG, Naiyan
Source: ZOJ Monthly, November 2009