백준 2904번 수학은 너무 쉬워

문제 링크입니다: https://www.acmicpc.net/problem/2904

에라토스테네스의 체를 이용하여 푸는 재밌는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 우선 에라토스테네스의 체를 이용해 소수를 모두 구합니다.

2. 이 후 입력받는 숫자들마다 소인수 분해를 진행하는데 해당 숫자에서 사용하는 소수의 개수와 모든 숫자에 대해 사용되는 소수의 개수를 모두 업데이트해줍니다.

3. 최대 공약수의 일부가 되기 위해서는 해당 소수가 N으로 나누었을 때 1 이상이여야합니다.

i) 조건이 성립한다면 해당 소수 * (N으로 나누었을 때 몫)만큼을 최대공약수에 곱해줍니다.

ii) 그리고 N개의 숫자 중 해당 소수의 개수가 부족한 숫자가 해당 소수가 많은 숫자로부터 소수를 받아옵니다.

4. 3번을 진행한 뒤 i)에서 구한 최대공약수와 ii)의 누적된 횟수를 출력합니다.

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 1000000 + 1;

 

int minFactor[MAX];

vector<int> prime;

 

void eratosthenes(void)

{

        minFactor[0] = minFactor[1] = -1;

        for (int i = 2; i < MAX; i++)

                 minFactor[i] = i;

 

        for (int i = 2; i*i < MAX; i++)

                 if (minFactor[i] == i)

                         for (int j = i * i; j < MAX; j += i)

                                 if (minFactor[j] == j)

                                          minFactor[j] = i;

 

        for (int i = 2; i < MAX; i++)

                 if (minFactor[i] == i)

                         prime.push_back(i);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        eratosthenes();

        //해당 소수가 총 몇번 사용되었는가?

        vector<int> usedPrime(prime.size(), 0);

        //idx번째 숫자를 소인수 분해 했을 때 각 소수의 개수

        vector<vector<int>> factor(N, vector<int>(prime.size(), 0));

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

 

                 for (int j = 0; j < prime.size(); j++)

                 {

                         //소인수 분해 진행

                         while (!(num % prime[j]))

                         {

                                 factor[i][j]++;

                                 usedPrime[j]++;

                                 num /= prime[j];

                                 if (num == 1)

                                          break;

                         }

                         if (num == 1)

                                 break;

                 }

        }

 

        int result = 1, cnt = 0;

        for (int i = 0; i < prime.size(); i++)

        {

                 int temp = usedPrime[i] / N; //최대 공약수의 일부가 될 수 있는지 판단

                 for (int j = 0; j < temp; j++)

                         result *= prime[i];

                 for (int j = 0; j < N; j++)

                         //적절히 나누어줘야한다.

                         if (temp > factor[j][i])

                                 cnt += temp - factor[j][i];

        }

        cout << result << " " << cnt << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~