求出两个数的最大公约数,如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
#include <utility>
template<typename NumType>
NumType gcd(NumType a, NumType b) {
while (b!=0) {
std::swap(a, b);
b %= a;
}
return a;
}
template<typename NumType> NumType stein_gcd(NumType a, NumType b) { NumType k = 0; while (a!=0 && b != 0) { if (b % 2 == 0) { if (a % 2 == 0) { k++; a /= 2; b /= 2; } else { b /= 2; } } else { if (a % 2 == 0) { a /= 2; } else { if (a < b) { std::swap(a, b); } a -= b; } } } if (a == 0) { a = b; } return a<<k; // 等价于a*pow(2,k) }