공약수

작성일 | In

[백준] 2436번 - 공약수

문제 링크

KOI 2011 초등부 문제.
최대공약수, 최소공배수 응용 문제이다.
임의의 두 자연수 x,y (x <= y)의 최대공약수는 다음과 같은 규칙으로 찾아낼 수 있다.

1
2
3
4
5
6
7
8
int findGcd(int x, int y) {
    while(x != 0) {
        int rest = y % x;
        y = x;
        x = rest;
    }
    return y;
}


임의의 두 자연수 x,y (x <= y)의 최대공약수가 a이고, 최소공배수가 b일 때, 아래와 같은 식이 성립한다.

1
2
3
b = xy / a

즉, ab = xy

이 문제는 최소공배수와 최대공약수가 주어지고, 이를 만족하는 두 자연수를 찾는 문제이다. 따라서 주어진 a와 b의 곱의 약수를 구한 뒤, 약수 중 두 수를 골라 그들의 최대공약수가 a와 같은지를 비교하면 된다.

문제를 풀면서 자료형을 잘 살펴야 함을 다시 한 번 상기할 수 있었다. a와 b를 곱하는 과정에서, long long형으로 캐스팅하지 않으면 곱 연산값은 long long형인 multi 변수에 넣기 전에 이미 오버플로우되어 잘못된 값이 저장될 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

int a,b;

int findGcd(int small, int big) {
    while(small != 0) {
        int rest = big % small;
        big = small;
        small = rest;
    }
    return big;
}

int main(void) {
    scanf("%d %d", &a, &b);

    long long multi = (long long)a*b;
    int r = sqrt(multi); // 두 자연수는 multi의 제곱근보다 클 수 없다.
    for(int i=r; i>=1; --i) {
        if(multi % i == 0) {
            int small = i;
            int big = multi / i;
            if(findGcd(small, big) == a) {
                printf("%d %d", small, big);
                exit(0);
            }
        }
    }
}
0%