Binary GCD (src/Math/binary_gcd.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-10-30 16:02:30+09:00
• Include: #include "src/Math/binary_gcd.hpp"

除算の代わりにシフト演算と引き算を使う速い互除法.
constexpr で呼べる.

名前	概要
binary_gcd(a,b)	整数 $a,b$ の最大公約数を返す.

Required by

• 二項係数 ($\mathbb{Z}/m\mathbb{Z}$) (src/Math/BinomialCoefficient.hpp)
• k乗根 ($\mathbb{F}_p$) (src/Math/mod_kth_root.hpp)
• テトレーション $a\upuparrows b$ ($\mathbb{Z}/m\mathbb{Z}$) (src/Math/mod_tetration.hpp)
• 指数に乗せられるModInt (src/Math/ModInt_Exp.hpp)
• 有理数 $\mathbb{Q}$ (src/Math/Rational.hpp)
• 約数配列 (src/NumberTheory/ArrayOnDivisors.hpp)
• 高速素因数分解など (src/NumberTheory/Factors.hpp)
• 原始根と位数 $\mathbb{F}_p^{\times}$ (src/NumberTheory/OrderFp.hpp)

Verified with

• test/alone/constexpr_binary_gcd.test.cpp
• test/alone/constexpr_factors.test.cpp
• test/alone/constexpr_mod_tetration.test.cpp
• test/alone/constexpr_orderfp.test.cpp
• test/alone/constexpr_rational.test.cpp
• test/aoj/0350.test.cpp
• test/aoj/1242.rational.test.cpp
• test/aoj/2003.rational.test.cpp
• test/aoj/2009.rational.test.cpp
• test/aoj/2159.rational.test.cpp
• test/aoj/NTL_1_D.test.cpp
• test/atcoder/abc212_g.test.cpp
• test/atcoder/abc228_e.test.cpp
• test/atcoder/abc248_g.test.cpp
• test/atcoder/abc335_g.test.cpp
• test/loj/6686.Dirich.test.cpp
• test/loj/6686.mul.test.cpp
• test/yosupo/binomial_coefficient.test.cpp
• test/yosupo/factorize.test.cpp
• test/yosupo/kth_root_mod.test.cpp
• test/yosupo/primitive_root.test.cpp
• test/yosupo/tetration_mod.test.cpp
• test/yukicoder/125.multiple_mobius.test.cpp
• test/yukicoder/125.phi.test.cpp
• test/yukicoder/1501.test.cpp
• test/yukicoder/1728.test.cpp
• test/yukicoder/2264.test.cpp
• test/yukicoder/2578.test.cpp

Code

#pragma once
#include <type_traits>
#include <algorithm>
#include <cstdint>
template <class Int> constexpr int bsf(Int a) {
 if constexpr (sizeof(Int) == 16) {
  uint64_t lo= a & uint64_t(-1);
  return lo ? __builtin_ctzll(lo) : 64 + __builtin_ctzll(a >> 64);
 } else if constexpr (sizeof(Int) == 8) return __builtin_ctzll(a);
 else return __builtin_ctz(a);
}
template <class Int> constexpr Int binary_gcd(Int a, Int b) {
 if (a == 0 || b == 0) return a + b;
 int n= bsf(a), m= bsf(b), s= 0;
 for (a>>= n, b>>= m; a != b;) {
  Int d= a - b;
  bool f= a > b;
  s= bsf(d), b= f ? b : a, a= (f ? d : -d) >> s;
 }
 return a << std::min(n, m);
}

#line 2 "src/Math/binary_gcd.hpp"
#include <type_traits>
#include <algorithm>
#include <cstdint>
template <class Int> constexpr int bsf(Int a) {
 if constexpr (sizeof(Int) == 16) {
  uint64_t lo= a & uint64_t(-1);
  return lo ? __builtin_ctzll(lo) : 64 + __builtin_ctzll(a >> 64);
 } else if constexpr (sizeof(Int) == 8) return __builtin_ctzll(a);
 else return __builtin_ctz(a);
}
template <class Int> constexpr Int binary_gcd(Int a, Int b) {
 if (a == 0 || b == 0) return a + b;
 int n= bsf(a), m= bsf(b), s= 0;
 for (a>>= n, b>>= m; a != b;) {
  Int d= a - b;
  bool f= a > b;
  s= bsf(d), b= f ? b : a, a= (f ? d : -d) >> s;
 }
 return a << std::min(n, m);
}

Back to top page