[ 백준 ] 2824 / 최대공약수

9798 단어 psbojboj

# Appreciation

/*
 * Problem :: 2824 / 최대공약수
 *
 * Kind :: Math
 *
 * Insight
 * - A = a1 * a2 * ... * an
 *   B = b1 * b2 * ... * bm
 *   + g11 = gcd(a1, b1)
 *     g12 = gcd(a1, b2)
 *     ... 라고 한다면
 *     gcd(A,B) = gcd(a1 * a2 * ... * an, b1 * b2 * ... * bm)
 *              = gcd(a1, b1 * b2 * ... * bm)
 *                * gcd(a2, b1/g11 * b2/g12 * ... * bm/g1m)
 *                * gcd(a3, b1/g11/g21 * b2/g12/g22 * ... * bm/g2m)
 *                  ...
 *     # gcd(a1, b1 * b2 * ... * bm)
 *       -> gcd(a1, b1 * b2 * ... * bm)
 *          = g11 * gcd(a1/g11, b2 * b3 * ... * bm)
 *            b1 /= g11
 *          = g11 * g12 * gcd(a1/g11/g12, b3 * b4 * ... * bm)
 *            b2 /= g12
 *          ...
 *          => gxy = gcd(ax, by)
 *             ans *= gxy
 *             ax /= gxy
 *             by /= gxy
 *
 * - 다음과 같은 입력이 들어왔다고 하자
 *   2
 *   20 15
 *   2
 *   10 10
 *   + A = 300 = 20 * 15
 *     B = 100 = 10 * 10
 *     # gcd(300, 100) = gcd(20 * 15, 10 * 10)
 *       -> ans = 1
 *          20 15
 *          10 10
 *
 *       -> ans = 10 <= gcd(20, 10) / g11
 *          2  15
 *          1  10
 *
 *       -> ans = 20 <= gcd(2, 10) / g12
 *          1  15
 *          1  5
 *
 *       -> ans = 20 <= gcd(15, 1) / g21
 *          1  15
 *          1  5
 *
 *       -> ans = 100 <= gcd(15, 5) / g22
 *          1  3
 *          1  1
 *
 * Point
 * - 최대공약수는
 *   #include <numeric> 에 있는
 *   gcd(A, B) 를 통해 쉽게 구할 수 있다!
 *
 * - ans 를 9 자리까지만 구하면 되기 때문에
 *   ans %= 10^9 로 구하지만
 *   만약 ans 가 10^9 보다 크지만 (9자리보다 길지만)
 *   답을 출력할 때 그 순간 ans 가 10^9 보다 작다면 (8자리 이하라면)
 *   9자리가 되도록 0 을 앞에 출력해주어야 한다
 *   + 코드의 경우 (bool) isBig 변수를 활용하여 이를 확인했으며
 *     printf 를 활용하였다
 *     # cout 에서는 setfill 을 활용해서 출력할 수도 있더라~
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <numeric>
// #include <iomanip>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    long A[N];
    for (int i=0; i<N; i++)
        cin >> A[i];
    int M; cin >> M;
    long B[M];
    for (int i=0; i<M; i++)
        cin >> B[i];

    // Process
    long ans = 1; /* 최대공약수 */
    bool isBig = false; /* ans 가 9자리 이상인지 확인 */
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            long gij = gcd(A[i], B[j]);
            ans *= gij;
            if (ans >= 1'000'000'000) { /* ans 가 9자리보다 길다면 */
                isBig = true; /* isBig 변수로 이를 체크 */
                ans %= 1'000'000'000; /* 10^9 로 나눈 나머지로 ans 를 갱신 */
            }
            A[i] /= gij;
            B[j] /= gij;
        }
    }

    // Control : Output
    if (isBig)
        printf("%09ld\n", ans);
        // cout << setfill('0') << setw(9) << ans << endl;
    else
        cout << ans << endl;
}

// Helper Functions
/* None */

좋은 웹페이지 즐겨찾기