This documentation is automatically generated by online-judge-tools/verification-helper
#include "src/math/BinaryGCD.hpp"
割り算を使わない高速な GCD
u64 binary_gcd(u64 x, u64 y)
:$x$ と $y$ の最大公約数を計算する.
u64 ctz(u64 x) { return countr_zero(x); }
u64 binary_gcd(u64 x, u64 y) {
if(!x || !y) return x | y;
u64 n = ctz(x), m = ctz(y);
x >>= n, y >>= m;
while(x != y) {
if(x > y) x = (x - y) >> ctz(x - y);
else y = (y - x) >> ctz(y - x);
}
return x << min(n, m);
}
#line 1 "src/math/BinaryGCD.hpp"
u64 ctz(u64 x) { return countr_zero(x); }
u64 binary_gcd(u64 x, u64 y) {
if(!x || !y) return x | y;
u64 n = ctz(x), m = ctz(y);
x >>= n, y >>= m;
while(x != y) {
if(x > y) x = (x - y) >> ctz(x - y);
else y = (y - x) >> ctz(y - x);
}
return x << min(n, m);
}