최대공약수와 최소공배수

최대공약수

최대공약수를 구하는 알고리즘으로 유명한 유클리드 호제법이 있습니다.

 

"두 개의 자연수 a, b에서 a를 b로 나눈 나머지 r이 있을 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다."

 

이 원리를 이용하여 a, b가 있을 때 b MOD r를 구하고 이를 r'라고 하면, r MOD r'를 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. (gcd)

 

그대로 코드로 표현해보면

int gcd(int a, int b) {
    int r;
    while(b) {
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

단, a > b는 이어야하기 때문에 b > a라면 두 숫자를 바꿔주는 과정이 필요합니다.

int gcd(int a, int b) {
    if(b > a) {
        int temp = a;
        a = b;
        b = temp;
    }
    int r;
    while(b) {
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

위 코드를 재귀로 표현할 수도 있습니다.

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

재귀호출을 이용하여 작성 시 두 수의 대소관계를 신경 쓸 필요가 없습니다.

최소공배수

최소공배수는 (최소공배수) * (최대공약수) = a * b 식을 이용합니다. (lcm)

 

(최소공배수) = (a * b) / (최대공약수)

최대공약수 = gcd(a, b)

(최소공배수) = (a * b) / gcd(a, b)

백준 문제

이제 이론을 알았으면 관련 문제를 풀어봅시다!

BOJ #1850 최대공약수

1850번: 최대공약수

 

https://www.acmicpc.net/problem/1850

자연수 A와 B가 주어지면 최대공약수를 1로 표현하는 문제입니다.

예제 규칙을 살펴보면 A와 B의 최대공약수만큼 1이 반복됩니다.

 

gcd()를 이용하여 코드로 짜줍시다!

// ...
typedef long long ll;

// ...

ll A, B;
cin >> A >> B;

for(int i = 0; i < gcd(A, B); i++) cout << "1";

// ...

다만, 입력되는 수가 2^63보다 작기 때문에 int가 아닌 long long으로 풀어야합니다.

BOJ #1934 최소공배수

1934번: 최소공배수

https://www.acmicpc.net/problem/1934

해당 문제는 테스트 케이스가 주어지고 A와 B의 최소공배수를 출력하는 문제입니다.

그래도 구현해주면,

// ...

int T;
cin >> T;

while(T--) {
    int a, b;
    cin >> a >> b;

    cout << (a * b) / gcd(a, b) << "\n";
}

// ...

 

끝!

 

 

Reference: https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95