test/alone/constexpr_binary_gcd.test.cpp

• View this file on GitHub
• Last update: 2024-08-23 12:46:00+09:00

Depends on

• Binary GCD (src/Math/binary_gcd.hpp)

Code

// competitive-verifier: STANDALONE

#include "src/Math/binary_gcd.hpp"

constexpr auto f= binary_gcd(2, 4);
static_assert(f == 2);
constexpr auto g= binary_gcd(1000000007, 1000000009);
static_assert(g == 1);
signed main() { return 0; }

#line 1 "test/alone/constexpr_binary_gcd.test.cpp"
// competitive-verifier: STANDALONE

#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);
}
#line 4 "test/alone/constexpr_binary_gcd.test.cpp"

constexpr auto f= binary_gcd(2, 4);
static_assert(f == 2);
constexpr auto g= binary_gcd(1000000007, 1000000009);
static_assert(g == 1);
signed main() { return 0; }

Back to top page