31 lines
420 B
Java
31 lines
420 B
Java
public static long gcd(long u, long v){
|
|
long t, k;
|
|
|
|
if (v == 0) return u;
|
|
|
|
u = Math.abs(u);
|
|
v = Math.abs(v);
|
|
if (u < v){
|
|
t = u;
|
|
u = v;
|
|
v = t;
|
|
}
|
|
|
|
for(k = 1; (u & 1) == 0 && (v & 1) == 0; k <<= 1){
|
|
u >>= 1; v >>= 1;
|
|
}
|
|
|
|
t = (u & 1) != 0 ? -v : u;
|
|
while (t != 0){
|
|
while ((t & 1) == 0) t >>= 1;
|
|
|
|
if (t > 0)
|
|
u = t;
|
|
else
|
|
v = -t;
|
|
|
|
t = u - v;
|
|
}
|
|
return u * k;
|
|
}
|