[algorithm] 최대 공배수, 최소 공배수

수학

최대공약수

두 수 이상의 여러 수의 공통인 약수(공약수) 중 가장 큰 수

최소 공배수

두 수 이상의 여러 수의 공통인 배수(공배수) 중 가장 작은 수

최대 공약수 & 최소 공배수 구하는 법

1. 모든 수가 서로수로 나눠질 때까지 나눈다.
2. 나누었던 수를 곱하면 최대 공약수이다.
3. 최소 공배수는 최대 공약수 * 서로수이다.

유클리드 알고리즘

두 자연수 a, b가 주어졌다.

가장 큰 값을 a, 다른 값 b, a와 b를 나눈 나머지를 n이라 했을 때,
n이 0일 경우 -> b는 최소 공배수가 된다.
그러지 않을 경우 -> a에 b값을 대입하고, b에 n의 값을 대입한다.
n이 0이 될 때까지 위를 반복한다.

만일 자연수가 n개일 때,
첫번째 값과 두번째 값을 대입한 uclid 호출하여 gcd를 구한 후,
이어서 다른 값과 gcd를 대입한 uclid를 호출하여 gcd를 구하는 과정을 반복한다.

#include <iostream>
using namespace std;

int uclid(int a, int b){
    int temp;
    if(b > a){
        temp = a;
        a = b;
        b = temp;
    }
    while(a % b != 0){
        temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}

gcd 합 구하기 문제

1. 조합으로 모든 쌍 구하기
2. uclid 알고리즘 거친 후 gcd 구하기
3. gcd를 더한 값 출력
4. test case 만큼 반복

#include <iostream>
#include <vector>
using namespace std;

long long gcdSum = 0;
int uclid(int a, int b){
    if(b > a){
        int temp = a;
        a = b;
        b = temp;
    }
    while(a % b != 0){
        int temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}
void combination(int count, vector<int> number, vector<int> realNum, int index){
    if(count == 0){
        int gcd = uclid(number[0], number[1]);
        gcdSum += gcd;
        return;
    }
    else if(index == realNum.size()) return;
    number.push_back(realNum[index]);
    combination(count- 1, number, realNum, index + 1);
    number.pop_back();
    combination(count, number, realNum, index + 1);
}
int main(void){
    int test;
    cin >> test;
    for(int i = 0; i < test; i++){
        int count;
        cin >> count;
        vector<int> number;
        while(count--){
            int num;
            cin >> num;
            number.push_back(num);
        }
        vector<int> combNumberVector;
        combination(2, combNumberVector, number, 0);
        
        cout << gcdSum << "\n";
        gcdSum = 0;
    }

}

 

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102702.cpp

jeongdaeun98/algorithm