forked from adnanaziz/EPIJudge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Gcd.java
32 lines (27 loc) · 886 Bytes
/
Gcd.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package epi;
import epi.test_framework.EpiTest;
import epi.test_framework.GenericTest;
public class Gcd {
@EpiTest(testDataFile = "gcd.tsv")
public static long GCD(long x, long y) {
if (x > y) {
return GCD(y, x);
} else if (x == 0) {
return y;
} 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, y is odd.
return GCD(x >>> 1, y);
} else if ((x & 1) != 0 && (y & 1) == 0) { // x is odd, y is even.
return GCD(x, y >>> 1);
}
return GCD(x, y - x); // Both x and y are odd.
}
public static void main(String[] args) {
System.exit(
GenericTest
.runFromAnnotations(args, "Gcd.java",
new Object() {}.getClass().getEnclosingClass())
.ordinal());
}
}