Hi Guys, I’ve been stuck for a couple of days trying to solve this problem BTCODE_A on spoj. I’ve understood that the gcd of (xs, ys) must divide any linear combination of xs and ys, which means xd = (axs + bys), yd = (axd + byd). However, in the solutions I found by other users, they are doubling gcd(xs, ys) until it reached gcd(xd, yd). If gcd(xs, ys) crosses gcd(xd, yd), then the result is “NO”. If it reached gcd(xd, yd), then the result is “YES”. I am having a hard time to figure out the proof and the relation between the two gcds. Why the gcd(xs, ys) is continuously doubled? Any proofs or hints appreciated. Thanks in advance!
The doubling of gcd, I strongly suspect, is due to constraints of-
c) Move to point (x+y, y)
d) Move to point (2*x, y)
Eg, if I have to move from 1,1 to 2,2-
x==>2x ==>2,1
x,y ===>y,x ==>1,2
x==>x2 ==>1*2==>2,2
But if we try the same for 3,3 , we cannot reach 3,3 from 1,1. We can reach 3,2 and 2,3 but NOT 3,3. If we try 2*x, it becomes 4. x,y==>x+y,y and x,y==>y,x will make either x or y odd, but not both.
Hence the GCD is doubled to check. Hope it helps and explains the pattern of doubling gcd which you saw!! 
(Do upvote if the explanation helps!!)
Yup! I got it. When you repeatedly use operations c and d, the gcd doubles! Thanks
Happy to help you dear!!