[BOJ 2904] 수학은 너무 쉬워

2904번: 수학은 너무 쉬워

 

예쁘게 구현한 것을 자랑하고 싶어 가져왔다. 관련 테크닉도 자주 쓰이는 듯 하니 기억하자.

 

최대공약수를 크게 만들려면 n개의 수에 소인수가 균등하게 분배되어야 하는 것이 자명하다. n개의 수를 모두 곱한 다음 최대한 비슷하게 다시 n개의 수로 쪼갠다고 생각해도 무방하다. 그러나 이동횟수도 구해야 하므로 처음 수는 저장해야 한다. 벡터에 모든 소인수를 저장하고, 맵에 각각의 수의 소인수분해 결과와 합친 결과를 저장한다. 그리고 모든 소인수에 대해 최대공약수와 이동횟수를 갱신해주면 답을 구할 수 있다.

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    scanf("%d",&n);
    map<int,int> m[100];
    map<int,int> p;
    vector<int> pp;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        for(int j=2;j*j<=x;j++){
	        if(x%j==0){
                int cnt=0;
                for(;x%j==0;x/=j) cnt++;
                m[i][j]=cnt;
                if(!p[j]) pp.push_back(j);
                p[j]+=cnt;
            }
        }
        if(x>1){
            m[i][x]=1;
            if(!p[x]) pp.push_back(x);
            p[x]+=1;
        }
    }
    int gcd=1,ans=0;
    for(int i=0;i<pp.size();i++){
        int k=p[pp[i]]/n;
        int mul=1;
        for(int j=0;j<k;j++) mul*=pp[i];
        gcd*=mul;
        for(int j=0;j<n;j++) if(m[j][pp[i]]<k) ans+=k-m[j][pp[i]];
    }
    printf("%d %d",gcd,ans);
}