公因公倍數

//-----------------------------------
//     Greatest Common Divisor
//-----------------------------------

//遞歸版

int gcd (int a, int b)  
{  
    return b? gcd (b, a%b): a; 
}

//慢速版,有'減'零風險

int gcd (int a,int b)
{ 
    while (a^b) a>b? a-=b: b-=a;
    return a;
} 

//有'除'零風險

int gcd (int a, int b)
{
    while ((a%=b) && (b%=a));
    return a + b;
}

//遞歸 Stein 算法

int gcd (int a,int b)
{
    static int A, B;
    if (a == 0) return b;
    if (b == 0) return a;
    A = a % 2;
    B = b % 2;
    if (!A && !B) return gcd (a/2, b/2) *2;
    if (A == 0)   return gcd (a/2, b  );
    if (B == 0)   return gcd (a  , b/2); 
    return gcd (abs(a-b), min(a,b));
}

//用位元算

typedef unsigned int U4B;

U4B gcd (U4B a, U4B b)
{ 
    if (!a || !b)     return a|b; 
    if (~a&1 && ~b&1) return gcd (a>>1,b>>1)<<1; 
    if (~a&1 &&  b&1) return gcd (a>>1,b   ); 
    if ( a&1 && ~b&1) return gcd (a   ,b>>1); 
    if (a > b)        return gcd (a-b ,b);  
                      return gcd (b-a ,a); 
}

//非遞歸 Stein 很多地方有快速版，跳略。

//-----------------------------------
//      Least Common Multiple
//-----------------------------------

//套定義

int lcm (int a, int b)
{
    return (a*b) / gcd (a,b);
}

//反向操作

int lcm (int a, int b)
{
    int A = a, B = b;
    while (a^b) 
        a>b ? (a-=b, A+=B): (b-=a, B+=A);
    return (A+B) / 2;
}

//縮成短碼

int lcm (int a, int b)
{
    int c = a*b;
    while (b^=a^=b^=a%=b);
    return c/a;
}

//寫成模版

template <int a, int b> struct Gcd {
    enum {v = Gcd<b,a%b>::v};
};
template <int a> struct Gcd <a,0> {
    enum {v = a};
};
template <> struct Gcd <0,0> {
    enum {v = ~0};
};
template <int a, int b> struct Lcm {
    enum {v = a*b/ Gcd<a,b>::v};
};