[백준 2824번] 최대공약수 (C++)

문제링크 : https://www.acmicpc.net/problem/2824

2824번: 최대공약수

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M;
    ll a[1000];
    ll b[1000];
    ll result = 1;
    bool check = 0;
    
    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++)
        {
            ll gcd_num = gcd(a[i], b[j]);
            result *= gcd_num;
            a[i] /= gcd_num;  //이미곱했으니 약분처리
            b[j] /= gcd_num;  
        
            if(result>=1000000000)
            {
                result%=1000000000;
                check = 1;         //9자리가 넘음
            }

        }
    }
    
    if (check)
    {
        printf("%09lld", result);  //9자리 출력
    }
    else
    {
        cout << result;
    }
    return 0;
}

각 값들에 대한 최대공약수를 구하고 이를 결과값에 곱해준다.

이때 각 값들을 방금 구한 최대공약수로 나눠줌으로써 중복으로 곱해지는 경우를 예방한다.

결과값이 9자리여야 하기 때문에. 9자리가 넘을 경우를 체크할 bool 변수 check를 통해 확인했다.