[백준]2904_수학은 너무 쉬워

https://www.acmicpc.net/problem/2904

Solved

✔ 알고리즘 분류: 정수론, 소수 판정
✔ 목표: 소인수분해한 여러 수들의 소수들을 종이에 적으며 이리저리 옮긴 후 종이에 적힌 모든 수의 최대공약수. 공약수가 되는 소수를 이용해서 N개의 자연수의 균형을 맞춰주는 것이 목표
✔ 풀이
1. 주어진 수들 각각을 소인수분해하면 어느 소수가 얼마만큼 있는지 cnt[i][j]에 저장. 숫자 24는 2 3개, 3이 1개 있으므로 cnt[24][2]=3, cnt[24][3]=1.
2. 숫자 i가 가진 소수의 개수를 totaclCount[i]에 저장
3. 최종적으로 종이 위의 n개의 수는 모두 totalCount[i]/n의 소수의 곱으로 구성된 값들이다.

#include <iostream>
#include <vector>
#define MAX 1000001
using namespace std;

bool e[MAX];
int n, a[100];
vector<int> prime;
int cnt[100][80000];  // 백만 루트 하면 80000 이정도 나옴
int totalCount[80000];  // 전체 숫자에서 소수가 나타난 횟수 
int gcdCount[80000];    // gcd가 될 것 같은 횟수 
int answer1, answer2;   // 가장 큰 점수, 최소 횟수  

void era() {
    e[1] = true;
    for (int i = 2; i < MAX; i++) {
        if (e[i]) continue;
        // i is prime 
        for (int j = i*2; j < MAX; j += i) {
            e[j] = true;
        }
    }
    for (int i = 2; i < MAX; i++) {
        if (!e[i]) { //e[i]가 거짓이라면
            prime.push_back(i);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    era();

    // 각 숫자별로 소수가 몇개씩 있을까????? ==> 소인수분해 
    for (int i = 0; i < n; i++) {
        int num = a[i];
        for (int j = 0; j < prime.size(); j++) {
            while (num % prime[j] == 0) { //a[i]에 prime[j]가 몇개 들어 있을까
                cnt[i][j]++;
                totalCount[j]++;
                num /= prime[j];
            }
        }
    }
    for (int i = 0; i < prime.size(); i++) {
        gcdCount[i] = totalCount[i] / n;
    }
    answer1 = 1;
    for (int i = 0; i < prime.size(); i++) {
        for (int j = 0; j < gcdCount[i]; j++) {
            answer1 *= prime[i];
        }
        // 각 숫자들에 대해서 GCD되기 위해서 소수가 얼마나 부족한지 확인해본다 
        for (int j = 0; j < n; j++) {
            if (cnt[j][i] < gcdCount[i]) {
                answer2 += gcdCount[i] - cnt[j][i];
            }
        }
    }
    cout << answer1 << ' ' << answer2 << '\n';
}