백준 2824 최대공약수 c++ (에라토스테네스의 체)

문제 출처 : https://www.acmicpc.net/problem/2824

2824번: 최대공약수

문제

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.(1 ≤ N ≤ 1000) 둘째 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다.

셋째 줄에 M이 주어진다.(1 ≤ M ≤ 1000) 넷째 줄에는 M개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를 곱하면 B가 된다.

출력

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

알고리즘 분류

• 수학
• 구현
• 정수론

풀이

이 문제는 숫자의 오버플로우를 해결하는 것이 중점이다.

 

첫 번째 풀이는 두 수 a와 b의 약수들을 2중 for문으로 서로 모두 비교해서 

두 약수 간의 최대공약수를 찾아서 곱해나갔고, 두 약수들은 최대공약수로 나눈 값으로

갱신해 줬다.

최대공약수를 찾는 데에는 '유클리드 호제법' 알고리즘을 사용하였다.

 

두 번째 풀이는 소수들을 대량으로 빠르고 정확하게 구하는 알고리즘인

'에라토스테네스의 체' 알고리즘과 해쉬 자료구조인 map을 사용하여 구현하였다.

약수는 1,000,000,000보다 작기 때문에 2부터 40000까지의 소수를 구하고,

(어떤 수의 소수 여부를 확인할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 되기 때문에40000*40000>=1,000,000,000)

두 수 a와 b의 약수들을 소인수분해하여 각각 map에 저장한다.

map의 key는 소인수,

map의 value는 소인수의 횟수

그 후, 하나의 map a를 탐색하면서, map a의 key와 map b의 key가 같다면,

둘 중 횟수가 적은 소인수를 횟수만큼 곱해준다.

 

 

유클리드 호제 문제 : https://ongveloper.tistory.com/106 

프로그래머스 멀쩡한 사각형 c++ (유클리드 호제)

 

 

코드1(2중for문)

#include<iostream>
#define INF 1000000000
using namespace std;

long long gcd(long long low, long long high) {
    return high % low ? gcd(high % low, low) : low;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    int a[1000], b[1000];
    long long answer = 1;
    bool isBigger=false;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            long long gc; // 두 약수의 최대공약수
            if(a[i]<b[j])
                gc = gcd(a[i], b[j]);
            else
                gc = gcd(b[i], a[j]);

            answer *= gc; 
            a[i] /= gc;
            b[j] /= gc;
            if (answer >= INF) { //INF보다 크거나 같으면 INF로 나누어주기
                answer %= INF;
;                isBigger = true;
            }

        }
    }

    if (isBigger)//INF보다 크지만 나머지 값이 앞부분이 0이 나올 수 있으니 9자리수를 맞춰줘야함
        printf("%09lld", answer);
    else
        cout << answer;



    return 0;
}

코드2(에라토스테네스의 체)

#include<iostream>
#include<map>
#include<algorithm>
#include<vector>

#define INF 1000000000

using namespace std;
vector <int> prime;
bool visited[40000];
map<int, int> a, b;
void make(int num, char ch) {
    if (ch == 'a') {
        for (auto o : prime) {
            if (num%o == 0) {
                a[o]++;
                make(num / o, 'a');
                return;
            }
        }
        if (num != 1) //num이 약수가 없으면
            a[num]++;
    }
    else {
        for (auto o : prime) {
            if (num%o == 0) {
                b[o]++;
                make(num / o, 'b');
                return;
            }
        }
        if (num != 1)//num이 약수가 없으면
            b[num]++;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    long long answer = 1;
    bool isBigger=false;
    for (int i = 2; i < 40000; i++) {//2부터 40000까지 소수 저장
        if (visited[i])
            continue;
        prime.push_back(i);
        for (int j = 2 * i; j < 40000; j += i) {
            visited[j] = true;
        }
    }



    cin >> n;
    for (int i = 0; i < n; i++) {//주어진 a배열의 수들을 소인수분해하여 map a에 저장
        int num;
        cin >> num;
        make(num, 'a');
    }
    cin >> m;
    for (int i = 0; i < m; i++) {//주어진 b배열의 수들을 소인수분해하여 map b에 저장
        int num;
        cin >> num;
        make(num, 'b');
    }

    for (auto o : a) {
        if (!b[o.first]) //map a엔 있지만, map b에 없으면 pass
            continue;
        int cnt = min(o.second, b[o.first]); //map a와 map b 의 소인수가 같을 때, 해당 소인수의 count가 적은 것을 가져온다.
        while (cnt--) { //pow(o.first,cnt)하면 값이 다르게 나와서 cnt수만큼 곱해주기
            answer *= o.first; 
            if (answer >= INF) { //INF보다 크거나 같으면 INF로 나누어주기
                answer %= INF;
                isBigger = true;
            }
        }
    }
    if (isBigger)//INF보다 크지만 나머지 값이 앞부분이 0이 나올 수 있으니 9자리수를 맞춰줘야함
        printf("%09lld", answer);
    else
        cout << answer;

    return 0;
}