[2609,1934,9613번] 최대공약수와 최소공배수

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

2609번: 최대공약수와 최소공배수

 

1. 최대공약수(Greatest Common Divisor) 구하기

유클리드 호제법(Euclidean algorithm)을 이용하는 방법입니다.

 

* 유클리드 호제법

a를 b로 나눈 나머지를 r이라고 할 때,

GCD(a,b) = GCD(b,r) 이다.

r이 0이면 그 때의 b가 최대공약수가 됩니다.

세 수의 최대공약수를 구해야할 때는 GCD(a,b,c) =  GCD(GCD(a,b),c) 로 구할 수 있습니다.

즉, 먼저 두 수의 최대공약수를 구한 값과 c와의 최대공약수를 구하면 됩니다.

 

2. 최소공배수(Least Common Multiple) 구하기

두 수의 최소공배수는 GCD를 이용하여 구할 수 있습니다.

두 수의 최대공약수를 g라고 하고 최소공배수를 l이라고 할 때,

l=(a*b)/g 입니다.

 

 

[코드]

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    if (a % b != 0) { //나머지가 0이 아니라면
    	//재귀호출을 하는데 b는 a자리로, a%b는 b자리로 들어가면서 gcd를 구해나간다.
        return gcd(b, a % b);
    }else { //나머지가 0이라면 그때의 b가 정답이 된다.
        return b;
    }
}
int lcm (int a, int b) {
    return a * b / gcd(a, b);
}
int main () {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << '\n';
    cout << lcm(a, b) << '\n';
    return 0;
}

 

[결과]

24 18
6
72

 

 

 

 

 

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

1934번: 최소공배수

최소공배수는 최대공약수를 이용하여 쉽게 구할 수 있습니다.

 

 

[코드]

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    if (b == 0) {
        return a; 
    }else {
        return gcd(b, a % b);
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        cout << a * b / gcd(a, b) << '\n';        
    }
    return 0;
}

[결과]

3 //input
1 45000 //input
45000
6 10 //input
30
13 17 //input
221

 

 

 

 

 

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

9613번: GCD 합

이 문제도 최대공약수 연습문제입니다.

주의해야할 점이라면 결과값을 저장하는 sum 변수의 자료형입니다.

int형일 경우 통과가 되지 않으며, long long형일 경우 통과가 됩니다.

 

왜 long long 형이어야 하는지는 sum에 들어갈 수 있는 최대값을 대략적으로 계산해보아야 합니다.

최대값은 만들어질 수 있는 쌍의 최대 개수 * 각 쌍의 최대값이 될 것입니다.

 

1. 문제에서 각 테스트케이스마다 입력으로 주어지는 n의 값의 범위는 1 < n ≤ 100 라고 하였으니, 최대인 100으로 정합니다.

그러면 100개의 수의 전체 쌍의 개수를 구해야 합니다.

첫번째부터 시작해서 쌍을 만들면 99가지, 98가지, 97, ... 그리고 1까지의 합이 전체 쌍의 개수가 되므로 \(\frac{99*100}{2} = 4950\)개 입니다.

 

2. 모든 수의 입력이 1,000,000이고 모든 쌍의 최대공약수 값이 1,000,000이라는 최악의 상황을 가정.

 

1, 2번 값을 곱하면 \(4950 * 1000000 = 4,950,000,000\)이 되는데 49억은 int 자료형으로 담을 수 없습니다.

int형의 최대값은 \(2^{31}-1 = 2,147,483,647\)

즉, 21억정도가 되므로 long long으로 변경해야 테스트케이스를 통과할 수 있습니다.

 

 

 

[코드]

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
int main () {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int arr[101];
        
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                sum += gcd(arr[i], arr[j]);
            }
        }
        cout << sum << '\n';
    }
    return 0;
}

[결과]

3 //input
4 10 20 30 40 //input
70
3 7 5 12 //input
3
3 125 15 25 //input
35