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 :)

The following is a possible proof:

The initial pair (

m,n), where 0 <m≤ncan be rewritten as (m,qm+r) whereq≥ 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 subtractqmfromnto make the next number zero and win.Case 2: If

r> 0 andq> 1, then the next pair is (m, (q-k)m+r), where 1 ≤k≤q. Ifk<qis chosen, then (q-k)m+r>mand the smaller number in the next pair ism. It is then guaranteed that the next remainder of dividing (q-k)m+rbymis non-zero asr> 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.