[c++] 백준 #2904 수학은 너무 쉬워 (190830)

< 풀이 >

주어진 연산을 너무 복잡하게 생각하지 말고 그냥 다 곱해버린다고 생각하면 편하다. 결국에는 특정한 소인수를 어느쪽에 넘겨서 최대공약수를 만드는데 전체 숫자의 곱은 일정하므로, 전체 숫자를 소인수 분해하면

이런 식으로 값이 나오니까 gca값을 구하면 된다.

변환 숫자의 경우에는 각각의 숫자에 대해서

이런 식이고 

이런 식이라면 a < 1, b < 3, c < 2인지 확인해서 그 차이만큼을 더해주면 된다.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;


#define NUM 1000010

int A[101];
int soinsu[1000010];
int gca[1000010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    for(int i=0; i<N;i++){
        cin >> A[i];
        int temp = A[i];
        for(int j=2; j<=A[i];j++){
            while(temp > 0 && (temp % j == 0)){
                temp /= j;
                soinsu[j]++;
            }
        }
    }
    
    for(int i=0; i<NUM;i++){
        if (soinsu[i] >= N){
            gca[i] = (soinsu[i]/N);
        }
    }
    
    int num_gca = 1;
    for(int i=0; i<NUM;i++){
        if (gca[i] > 0){
            for(int j=0; j<gca[i];j++){
                num_gca *= i;
            }
        }
    }

    int ans = 0;
    for(int n=0;n<N;n++){
        vector<int> cur(NUM, 0);
        int temp = A[n];
        for(int j=2; j<=A[n];j++){
            while(temp > 0 && (temp % j == 0)){
                temp /= j;
                cur[j]++;
            }
        }
        for(int i=0; i<NUM;i++){
            if (cur[i] < gca[i]){
                ans += gca[i] - cur[i];
            }

        }
    }

    cout << num_gca << " " << ans << '\n';
    return 0;
}