티스토리 뷰

Programming/PS

최대공약수와 최소공배수

하늘빛QP 2019. 12. 22. 17:53

최대공약수

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

 

"두 개의 자연수 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번: 최대공약수

모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다.

www.acmicpc.net

 

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번: 최소공배수

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

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

'Programming > PS' 카테고리의 다른 글

최대공약수와 최소공배수  (0) 2019.12.22
댓글
댓글쓰기 폼