Binary GCD (位元 GCD)
(library/math/binary-gcd.hpp)

• View this file on GitHub
• Last update: 2023-04-03 17:58:04+08:00
• Include: #include "library/math/binary-gcd.hpp"

使用方法

long long a, b;
long long g = binary_gcd(a, b);

Required by

• Discrete Log (離散對數 $a^x \equiv b \pmod m$) (library/math/discrete-log.hpp)
• Integer Factorization (Pollard Rho 質因數分解) (library/math/factorize.hpp)

Verified with

• test/math/binary-gcd/aoj-ntl-Least-Common-Multiple.test.cpp
• test/math/discrete-log/yosupo-Discrete-Logarithm.test.cpp
• test/math/factorize/aoj-ntl-Prime-Factorize.test.cpp
• test/math/factorize/yosupo-Factorize.test.cpp

Code

#pragma once

namespace felix {

template<class T>
inline T binary_gcd(T a, T b) {
	if(a == 0 || b == 0) {
		return a | b;
	}
	int8_t n = __builtin_ctzll(a);
	int8_t m = __builtin_ctzll(b);
	a >>= n;
	b >>= m;
	while(a != b) {
		T d = a - b;
		int8_t s = __builtin_ctzll(d);
		bool f = a > b;
		b = f ? b : a;
		a = (f ? d : -d) >> s;
	}
	return a << (n < m ? n : m);
}

} // namespace felix

#line 2 "library/math/binary-gcd.hpp"

namespace felix {

template<class T>
inline T binary_gcd(T a, T b) {
	if(a == 0 || b == 0) {
		return a | b;
	}
	int8_t n = __builtin_ctzll(a);
	int8_t m = __builtin_ctzll(b);
	a >>= n;
	b >>= m;
	while(a != b) {
		T d = a - b;
		int8_t s = __builtin_ctzll(d);
		bool f = a > b;
		b = f ? b : a;
		a = (f ? d : -d) >> s;
	}
	return a << (n < m ? n : m);
}

} // namespace felix

Back to top page