[Codeforces 1062B] Math

[Codeforces 1062B] Math

문제 설명 : 

임의의 수 n이 주어졌을 때, 두 가지 종류의 연산을 수행할 수 있다. 하나는 n에다가 임의의 수 x를 곱할 수 있고, 다른 하나는 (현재 n이 제곱수 일 때)루트를 취할 수 있다. 이 두 연산을 사용하여 n을 최대한 작게 만들고, 그 수행 횟수를 구하는 문제이다.

풀이 : 

이 문제와 같이 어떤 수가 주어지고, 그 숫자에 연산을 취해서 값이 변해나가는 유형의 문제는 본인이 직접 예시 숫자들을 몇 개 끄적여보면서 규칙성(혹은 최적의 방법)을 찾아나가야 한다.

n을 최대한 작게 만드는게 목표이므로 나는 루트를 최대한으로 많이 취해야 할 것이다. 따라서 루트 연산이 가능한 형태로 n을 가공해야 한다. 루트 연산은 소인수들의 지수들이 모두 짝수여야만 가능하다. 또한 최대한 많이 루트를 취해야하므로 지수가 2의 거듭제곱 꼴이어야 한다. 2^6으로 예를 들면 지수인 6보다 큰 수 중에서 가장 작은 2의 거듭제곱인 8이 지수가 되어야 한다. 따라서 2^2를 곱해야 한다. 

즉 이 문제는 초기의 n을 소인수분해하여 소인수들의 형태를 파악하고, 소인수들의 지수들이 2의 거듭제곱이 되도록 어떤 수 x를 곱한 다음에 계속 루트를 취해주면 가장 빨리 n을 줄일 수 있다.

주의할 점 : 

처음부터 n의 소인수들의 지수들이 2의 거듭제곱꼴인 형태 (= 아무 것도 곱할 필요가 없는 상태) 라면 답을 1을 줄여야 한다. 이것에 대한 예외처리만 해주자.

배운 점 : 

-

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
/****************************Contest Template******************************/
 
 
int main(){
    ll n;   scanf("%lld",&n);
 
    map<ll,ll> mp;
    for(int i=2 ; i*i<=n ; i++){
        while(n%i==0) {
            mp[i]++;
            n/=i;
        }
    }
    if(n>1) mp[n]++;
 
    set<ll> pow2;
    for(int i=1 ; i<=62; i++){
        pow2.insert((ll)pow(2,i));
    }
 
    ll max_cnt=0;
    int is_same=1,all_1=1;
    auto it=mp.begin();
    int last=it->second;
    ll base=1;
 
    for(auto here:mp){
        base*=here.first;
        max_cnt=max(max_cnt,here.second);
        if(last!=here.second)
            is_same=0;
        last=here.second;
        if(here.second>=2) all_1=0;
    }
    
    int ans;
    if(pow2.count(max_cnt) && is_same){
        ans=0;
    }
    else {
        ans=1;
        ll exp=1;
        for(;exp<max_cnt ; exp*=2);
        max_cnt=exp;
    }
 
    while(max_cnt>1){
        ans++;
        max_cnt/=2;
    }
    if(all_1) ans=0;
    printf("%lld %d\n",base,ans);
    return 0;
}