[BOJ] 2094 수학은 너무 쉬워

전혀 쉽지 않은 문제였다. 각 값을 소인수분해 한 결과를 vector에 저장하고, 해당 소인수분해 결과를 종합해서 입력된 값들이 가질 수 있는 최대공약수를 구하고, 각각의 값들이 해당 최대공약수를 만족하기 위해 필요한 값의 갯수를 찾아서 합치면 된다. 

 

어찌보면 그냥 수학 문제인데, 생각보다 많이 어려웠다.  

 

#include <iostream>
#include <utility>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

int numbers[101], N, sieve[1001];
vector<pair<int,int>> datas[101];
map<int,int> sum;
pair<int,int> dummy;

void print_vector(){
  for(int i = 0 ; i < N; i++){
    vector<pair<int,int>> target = datas[i];
    printf("%d : ", i);
    for(int j = 0; j < (int) target.size(); j++){
      printf("(%d %d) ", target[j].first, target[j].second);
    }
    printf("\n");
  }
}

int main(){
  scanf("%d", &N);
  for(int i = 0 ; i < N ; i++){
    scanf("%d", &numbers[i]);
  }

  for(int i = 2; i < 1001; i++) {
    sieve[i] = 1;
  };

  // 에라토스테네스의 체
  for(int i = 2 ; i < 1001; i++){
    if(!sieve[i]) continue;
    for(int j = i * 2; j < 1001; j += i){
      sieve[j] = 0;
    }
  }

  // 각 수를 소인수분해한 결과를 datas에 넣기
  for(int i = 0 ; i < N ; i++){
    int data = numbers[i];
    
    for(int j = 0 ; j < 1001; j++){
      if(!sieve[j]) continue;
      int count_common_divider = 0;
      
      while((data % j) == 0){
        data /= j;
        count_common_divider++;
      }

      if(count_common_divider){
        dummy.first = j;
        dummy.second = count_common_divider;
        datas[i].push_back(dummy);
      }

      if(data == 1) break;
    }

    if(data != 1){
      datas[i].push_back(make_pair(data, 1));
    }
  }

  print_vector();

  // 모든 수를 곱한 결과를 Map에 넣기
  for(int i = 0 ; i < N ; i++){ 
    vector<pair<int,int>> target = datas[i];

    for(auto tup : target){
      map<int,int>::iterator it = sum.find(tup.first);

      if(it != sum.end()){
        it->second += tup.second;
      }
      else {
        sum.insert(tup);
      }
    }
  }

  int total = 1;
  int count = 0;

  // 생성할 수 있는 최댓값과, 최댓값을 생성하기 위해 필요한 수의 갯수를 구한다.
  for(map<int, int>::iterator it = sum.begin() ; it != sum.end(); ++it){
    it->second /= N;
    // printf("(%d %d)\n", it->first, it->second);
    for(int i = 0 ; i < it->second; i++){
      total *= it->first;
    }
    count += it->second;
  }

  int result = 0;
  int need_to_change;

  // 하나의 수에 대해서, 생성할 수 있는 최대공약수와 갯수차이를 구한다.
  // 각각의 숫자에 대해서 대해서 
  for(int i = 0 ; i < N ; i++){
    vector<pair<int,int>> target = datas[i];

    // 갯수 차이는 처음엔 필요한 수의 갯수로 초기화
    need_to_change = count;

    // 해당 숫자의 약수들에 대해서
    for(auto got : target){
      map<int, int>::iterator it = sum.find(got.first);

      printf("%d %d %d\n", got.first, it->second, got.second);
      // 필요한 약수보다 적을 때 현재 가진 양만큼 제거한다.
      if(it->second > got.second){
        need_to_change -= got.second;
      }

      // 필요한 약수보다 많으면 이미 모두 충족됬으므로 필요한 양만큼 제거한다.
      else {
        need_to_change -= it->second;
      }
    }
    result += need_to_change;
  }

  printf("%d %d", total, result);

  return 0;
}