[BOJ] 백준 2824 - 최대공약수

문제 링크

www.acmicpc.net/problem/2824

2824번: 최대공약수

 

풀이

수가 매우 크기 때문에 $a, b$를 long long으로 표현할 수 없습니다.

$a, b$를 소인수분해한 뒤, 겹치는 소인수를 모두 곱해주는 방식으로 정답을 구하면 됩니다.

 

근데 출력조건이 너무 불친절합니다. 9자리까지 출력해야 하는데, 만약 정답이 123,456이면 "123456"을, 1,000,123,456이면 leading zero를 포함하여 "000123456"을 출력해야 합니다. 계산 과정 중 9자리를 넘어가면 따로 체킹을 하고 0을 출력해주도록 합시다.

 

정답 코드

#include <bits/stdc++.h>

#define ft first
#define sd second
using namespace std;
using ll = long long;
const int MOD = 1'000'000'000;
bool c = false;
int n, m;
map<ll, int> a, b;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    ll x;
    for (int i = 0; i < n; i++) {
        cin >> x;
        for (int j = 2; j * j <= x; j++) {
            while (x % j == 0) {
                a[j]++;
                x /= j;
            }
        }
        if (x > 1) a[x]++;
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x;
        for (int j = 2; j * j <= x; j++) {
            while (x % j == 0) {
                b[j]++;
                x /= j;
            }
        }
        if (x > 1) b[x]++;
    }
    auto pa = a.begin(), pb = b.begin();
    ll ans = 1;
    while (pa != a.end() && pb != b.end()) {
        if (pa->ft > pb->ft) {
            pb++;
        } else if (pa->ft < pb->ft) {
            pa++;
        } else {
            int cnt = min(pa->sd, pb->sd);
            while (cnt--) {
                ans *= pa->ft;
                if (ans >= MOD) {
                    c = true;
                    ans %= MOD;
                }
            }
            pa++;
            pb++;
        }
    }
    if (c) {
        cout.width(9);
        cout.fill('0');
    }
    cout << ans;
}