
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) Input 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. Output 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. Sample Input 5 1 1 10 3 4 Sample Output 2 14 Author: WANG, Naiyan Source: ZOJ Monthly, November 2009 