Binary GCD
(src/math/BinaryGCD.hpp)

• View this file on GitHub
• Last update: 2024-06-01 01:21:46+09:00
• Include: #include "src/math/BinaryGCD.hpp"

割り算を使わない高速な GCD

使い方

• u64 binary_gcd(u64 x, u64 y)：$x$ と $y$ の最大公約数を計算する．
  • $O(\log(x + y))$ 時間

Verified with

• test/math/BinaryGCD.test.cpp

Code

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);
}

Back to top page