mooyyu

M7 - Stein算法-最大公约数

c++11 math

template< class type >
type stein(type a, type b) {
	unsigned c = 0;
	while (~a & 1u && ~b & 1u) a >>= 1u, b >>= 1u, ++c;
	while (~b & 1u) b >>= 1u;
	do {
		while (~a & 1u) a >>= 1u;
		if (a < b) swap(a, b);
	} while ((a = a - b >> 1u));
	return b << c;
}