Hackerrank Ad Infinitum - Math Programming Contest June'14 Possible Path Solution

Hackerrank Ad Infinitum - Math Programming Contest June'14 Possible Path: https://www.hackerrank.com/contests/infinitum-jun14/challenges/possible-path

Hackerrank Ad Infinitum - Math Programming Contest June'14 Possible Path editorial: https://www.hackerrank.com/contests/infinitum-jun14/challenges/possible-path/editorial
& https://hr-filepicker.s3.amazonaws.com/infinitum-jun14/editorials/2372-possible-path.pdf

Let gcd(a, b) be the largest positive integer that divides both a and b. Assume
gcd(0, 0) = 0. Negative a and b are allowed, but gcd(a, b) is always nonnegative.
When traveling from (a, b) to a next point, the gcd of the points is maintained.
To show this, we first notice that any common divisor of a and b divides a + b and
a−b. So in particular, the greatest one, gcd(a, b), divides a+b and a−b. Therefore,
gcd(a, b) divides gcd(a + b, b) and gcd(a − b, b). Also, a = (a + b) − b = (a − b) + b, so
by the same argument, gcd(a+b, b) and gcd(a−b, b) also divides gcd(a, b). Therefore
they must all be equal.
So, if gcd(a, b) 6= gcd(x, y), the answer is immediately “NO”, because we can
only reach points with the same gcd. The more surprising fact is that if gcd(a, b) =
gcd(x, y), then the answer is “YES”!
To show this, first note that the individual traversal operations are reversible.
For example, from (a, b), if we go to (a + b, b), we can go back to (a, b) because
(a, b) = ((a + b) − b, b). Specifically, the first and third kinds of traversals are reverse
operations of each other, and the same is true for the second and fourth. So instead
of saying “(a, b) can reach (x, y)”, we say instead “(a, b) is connected to (x, y)” to
emphasize the reversibility of the traversal.

Hackerrank Ad Infinitum - Math Programming Contest June'14 Possible Path Solution: http://ideone.com/tCsDBb

#include <iostream>
#include <cstdio>
using namespace std;

long long int gcd(long long int u, long long int v) {
    if(u==v) return u;
    if(u==0) return v;
    if(v==0) return u;
    if(~u & 1) {
        if(v&1) return gcd(u>>1, v);
        else return gcd(u>>1, v>>1)<<1;
    }
    if(~v & 1) return gcd(u, v>>1);
    if(u>v) return gcd((u-v)>>1, v);
    return gcd((v-u)>>1, u);
}

int main() {
    int t;
    long long int a, b, x, y, m, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld%lld%lld", &a, &b, &x, &y);
        m=gcd(a, b), n=gcd(x, y);
        if(m==n) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}