public static long GCD(long x, long y) {
        if (x == 0) {
            return y;
        } else if (y == 0) {
            return x;
        } else if ((x & 1) == 0 && (y & 1) == 0) {  // x and y are even.
            return GCD(x >> 1, y >> 1) << 1;
        } else if ((x & 1) == 0 && (y & 1) != 0) {  // x is even, and y is odd.
            return GCD(x >> 1, y);
        } else if ((x & 1) != 0 && (y & 1) == 0) {  // x is odd, and y is even.
            return GCD(x, y >> 1);
        } else if (x > y) {  // both x and y are odd, and x > y.
            return GCD(x - y, y);
        }
        return GCD(x, y - x);  // both x and y are odd, and x <= y.
    }