문제 정의 및 수학적 배경

주어진 $n$개의 정수 배열에 대해, 전체 원소의 최대공약수(GCD)와 최소공배수(LCM)의 곱이 모든 원소의 곱과 일치하는지 판별해야 합니다. 이를 수식으로 표현하면 다음과 같습니다.

$$ \text{LCM}(a_1, a_2, \dots, a_n) \times \gcd(a_1, a_2, \dots, a_n) = a_1 \times a_2 \times \dots \times a_n $$

직접 계산 방식의 한계

가장 직관적인 접근법은 실제 GCD, LCM, 그리고 배열의 전체 곱을 각각 계산한 뒤 비교하는 것입니다. 하지만 데이터의 범위가 커질 경우, LCM과 전체 곱은 long long 자료형의 표현 범위를 초과하여 오버플로우(Overflow)가 발생합니다. 따라서 실제 값을 직접 계산하여 비교하는 방식은 사용할 수 없습니다.

접근법 1: 소인수분해를 활용한 지수 비교

두 정수가 동일하다면, 그들은 반드시 동일한 소인수를 가지며 각 소인수의 지수 또한 같아야 합니다. 이 수학적 성질을 이용하면 큰 수를 직접 계산하지 않고도 등식의 성립 여부를 확인할 수 있습니다.

여러 정수의 LCM은 각 소인수 중 가장 큰 지수를 취하고, GCD는 가장 작은 지수를 취합니다. 해시 맵(Hash Map)을 사용하여 $ \text{LCM} \times \gcd $ 의 소인수 지수 합과 $ \prod a_i $ 의 소인수 지수 합을 각각 기록한 뒤, 두 맵이 동일한지 비교합니다.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

int compute_gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

void process_test_case() {
    int n;
    if (!(cin >> n)) return;

    unordered_map<int, int> prod_prime_counts;
    unordered_map<int, int> lcm_gcd_prime_counts;
    int current_gcd = 0;

    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        current_gcd = compute_gcd(current_gcd, val);

        int temp = val;
        for (int p = 2; p * p <= temp; ++p) {
            if (temp % p == 0) {
                int count = 0;
                while (temp % p == 0) {
                    temp /= p;
                    count++;
                }
                prod_prime_counts[p] += count;
                lcm_gcd_prime_counts[p] = max(lcm_gcd_prime_counts[p], count);
            }
        }
        if (temp > 1) {
            prod_prime_counts[temp] += 1;
            lcm_gcd_prime_counts[temp] = max(lcm_gcd_prime_counts[temp], 1);
        }
    }

    int temp_gcd = current_gcd;
    for (int p = 2; p * p <= temp_gcd; ++p) {
        if (temp_gcd % p == 0) {
            int count = 0;
            while (temp_gcd % p == 0) {
                temp_gcd /= p;
                count++;
            }
            lcm_gcd_prime_counts[p] += count;
        }
    }
    if (temp_gcd > 1) {
        lcm_gcd_prime_counts[temp_gcd] += 1;
    }

    if (prod_prime_counts == lcm_gcd_prime_counts) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) process_test_case();
    }
    return 0;
}

접근법 2: 수학적 최적화 및 서로소 판별

위 접근법을 더욱 최적화할 수 있습니다. 수학적 분석을 통해, $n \ge 3$ 인 경우 해당 등식이 성립하기 위한 필요충분조건은 배열의 모든 원소가 쌍별로 서로소(Pairwise Coprime) 임을 도출할 수 있습니다.

증명: 두 수 $a, b$ 가 서로소라면 $\gcd(a,b)=1$, $\text{lcm}(a,b)=ab$ 이므로 $1 \times ab = ab$ 가 성립합니다. 하지만 세 수 이상의 집합에서 만약 두 수가 공통 소인수를 가진다면, LCM을 구할 때 해당 소인수의 최대 지수만 반영되는 반면 전체 곱에는 모든 지수가 반영되므로 등식이 깨지게 됩니다. 단, $n \le 2$ 인 경우 두 수가 서로소가 아니더라도 $\gcd(a,b) \times \text{lcm}(a,b) = ab$ 항등식에 의해 항상 참이 됩니다.

따라서 $n \ge 3$ 일 때, 모든 원소를 소인수분해하면서 발견된 소인수를 해시 세트(Hash Set)에 저장합니다. 만약 이미 세트에 존재하는 소인수가 다시 발견된다면, 두 수 이상이 공통 소인수를 가진다는 의미이므로 즉시 조건 불일치를 출력하면 됩니다.

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

void process_optimized_case() {
    int n;
    if (!(cin >> n)) return;

    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    // n이 2 이하인 경우 수학적 항등식에 의해 항상 성립
    if (n <= 2) {
        cout << "Yes\n";
        return;
    }

    unordered_set<int> seen_primes;

    for (int i = 0; i < n; ++i) {
        int temp = arr[i];
        for (int p = 2; p * p <= temp; ++p) {
            if (temp % p == 0) {
                // 이미 발견된 소인수라면 쌍별로 서로소가 아님
                if (seen_primes.count(p)) {
                    cout << "No\n";
                    return;
                }
                seen_primes.insert(p);
                while (temp % p == 0) {
                    temp /= p;
                }
            }
        }
        if (temp > 1) {
            if (seen_primes.count(temp)) {
                cout << "No\n";
                return;
            }
            seen_primes.insert(temp);
        }
    }

    cout << "Yes\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) process_optimized_case();
    }
    return 0;
}