[GCD, LCM] 유클리드 호제법

유클리드 호제법?

두 수의 최대 공약수를 O(lgN)만에 구하는 방법이다.

생각보다 자주 까먹으니까.. 틈틈이 시간 나면 한 번씩 봐주자.

재귀 함수 구현

int gcd(int a, int b)
{
    if(b == 0) return a;
    else return gcd(b, a % b);
}

반복문 구현

전제 조건 : a > b
while(1)
{
    int r = a % b;
    if(r == 0) return b;
    
    a = b;
    b = r;
}

최소 공배수는?

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

최소 공배수에서 gcd(a, b)를 3번이나 해주는 이유는 특정 구간에서 오버플로우의 방지를 막기 위해서이다.