수학은 너무 쉬워 (boj 2904)

수학은 너무 쉬워 문제는 소수를 구하고, 그 소수로 소인수분해를 하는 문제입니다.

최대 공약수라는게 모든 수가 갖고 있는 소수들의 곱으로 나타내지기 때문에 N개의 숫자를 각각 소인수분해하여 N개의 숫자를 통틀어서 어떤 소수를 몇개나 갖고있게 되는지 알게된다면 문제는 쉬워집니다.

예를 들어 8 24 9는

8 = 2^3

24 = 2^3 * 3

9 = 3^2

따라서 2가 6개, 3이 3개입니다.

숫자의 갯수가 3이므로 2를 2개씩 나눠가지고, 3을 한 개 씩 나눠가지면 최대공약수가 2^2 * 3 = 12가 됩니다.

그리고 움직이는 횟수는 9가 2를 두 개 받았고, 8이 3을 하나 받았으니 3개가 될거에요.

 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>

int N;
int arr[110];
std::vector<int> primes;
int visit[1000010];
int count[100000];
int count2[110][100000];
int maxScore = 1;
int moveCount;

int main() {
    // 에라토스테네스의 체
    for (int i = 2; i < 1000000; i++) {
        if (!visit[i]) {
            primes.push_back(i);
            for (int j = i; j < 1000000; j += i) {
                visit[j] = 1;
            }
        }
    }

    scanf("%d", &N);

    for (int n = 0; n < N; n++) {
        // 입력
        scanf("%d", &arr[n]);

        // 구해둔 소수들로 나눠봄
        for (int i = 0; i < primes.size(); i++) {
            int p = primes[i];
            if (p > arr[n])
                break;

            // 입력받은 수가 해당 소수로 더이상 나눠지지 않을때까지 나눔
            while (arr[n] % p == 0) {
                // 나누기
                arr[n] /= p;

                // 해당 소수가 전체 입력에서 몇번이나 나왔는지 기록
                count[i]++;

                // 현재 입력 값이 해당 소수를 몇 개나 갖고 있는지 기록
                count2[n][i]++;
            }
        }
    }

    // 모든 소수에 대해 반복
    for (int i = 0; i < primes.size(); i++) {
        // 해당 소수를 전체 입력의 수 N 으로 나눈 c는 최대 공약수에 포함될 수 있음
        // 예를 들어 N이 10이고, 소수 2가 N개의 숫자에서 20번 나왔으면
        // c 는 2이고, 2 ^ 2 = 4
        // 4는 최대 공약수에 포함됨
        int c = count[i] / N;
        if (c == 0)
            continue;

        // 최대 공약수에 포함
        maxScore *= (int) pow(primes[i], c);

        for (int n = 0; n < N; n++) {
            // N 개의 숫자가 모두 2를 2개씩 갖고 있어야 총 20번의 2가 나올 수 있는데
            // 소수 2를 2개 미만으로 갖고있는 수가 있다면 반드시 2개 초과하여 갖고 있는 수가 있기에
            // 이를 나눠줘야함
            if (count2[n][i] < c) {
                // 모자란 2의 갯수만큼 moveCount(움직인 횟수)가 증가
                moveCount += c - count2[n][i];
            }
        }
    }

    printf("%d %d", maxScore, moveCount);
    return 0;
}