最大公约数 and 最小公倍数

[bruc...@gmail.com]

// 求最大公约数(greatest common divisor)
template <typename T>
inline T GCD( T a, T b )
{
// 此函数能够被执行的前提是a和b都是自然数
assert( a >= 0 );
assert( b >= 0 );

// 一个用于交换和存放余数的临时变量
T c;
// 确保a大于等于b
if( a < b )
{
c = a;
a = b;
b = c;
}
// 辗转相除法求最大公约数
for( ; c=a%b,c!=0; a=b,b=c );

return b;
}

// 求最小公倍数(lease common multiple)
template <typename T>
inline T LCM( T a, T b )
{
assert( a >= 0 );
assert( b >= 0 );

T t = a*b;
T c;
if( a < b )
{
c = a;
b = a;
a = c;
}
for( c=a%b; c!=0; c=a%b )
{
a = b;
b = c;
}
return t/b;
}

---