By MohamedHamada_, history, 13 months ago, , I was solving the problem UVa 10368 and after thinking for a while i came up with this solution:

The first player have a number n%m == 0 or n/m > 1 is the winner and got AC ! :D

I just observed this solution when i tried some numbers on a paper but i actually don't have a rigorous proof for that ! could you demonstrate why this solution works ?

Thanks in advance :) Comments (3)
 » 13 months ago, # | ← Rev. 5 →   The following is a possible proof: The initial pair (m, n), where 0 < m ≤ n can be rewritten as (m, qm + r) where q ≥ 0 and 0 ≤ r ≤ m - 1 are quotient and remainder of the integral division div(n,m), respectively. Case 1: If r = 0, then the game is over, as the player can immediately subtract qm from n to make the next number zero and win. Case 2: If r > 0 and q > 1, then the next pair is (m, (q - k)m + r), where 1 ≤ k ≤ q. If k < q is chosen, then (q - k)m + r > m and the smaller number in the next pair is m. It is then guaranteed that the next remainder of dividing (q - k)m + r by m is non-zero as r > 0. Consequently, it is guaranteed that the other player does not win in the next play. The following is a slight update to your program using the standard library function div(n,m).
 » In codechef may long challenge divB, Qn2 "matches" is same as above. I implemented your logic and got WA. It seems that there may be weak testcases at uva platform. And i still dont know at which testcase , this logic is getting WA.
 » whoever has n/m > 1 first approach works too.