B. Math

어떤 수 n이 주어졌을 때 두가지 연산을 할 수 있다.

1. *x

2. sqrt(n) : 결과가 자연수여야 하고 sqrt(n)^2 == n이어야 함

이런 연산을 통해 만들 수 있는 가장 작은 수와 그 수에 도달하기까지 최소연산의 횟수를 출력해야 한다.

입력범위 밖의 값이긴 하지만 n=19293750 일때를 생각해 보자.

만들 수 있는 가장 작은 수를 만들어야 하고 우리가 가진 연산중 값이 작아지는 연산은 2번연산 밖에 없다.

한마디로 sqrt를 더이상 취할 수 없는 수가 우리가 원하는 가장 작은 수가 된다.

sqrt를 최대한 취한다면 result(n)은 결국 1승짜리 소수의 곱으로 나타날 것이다.

n을 소수들로 표현해보면

n = 19293750 = 2 * 3^2 * 5^5 * 7^3

이고 우리가 원하는 결과는 2*3*5*7 = 210 이 될 것이다. 저기서 더 줄일 수 있는 방법이 있는가? 없다.

그렇다면 1번 연산은 n을 sqrt취할 수 있도록 만들어 주는 값을 곱하는 역할만을 할 것이다.

또한 곱하는 수 x에는 제한이 없으므로 result = sqrt(sqrt(n*x))... 이런식으로 x를 한번만 곱한다던가 혹은

아무것도 곱하지 않고 sqrt만 취하는 형태가 될 것이다. sqrt는 지수를 절반으로 낮춰주므로 우리는

n에다가 2^7 * 3^6 * 5^3 * 7^5를 한번 곱해주고 sqrt를 3번 취해주면 될 것이다.

해법

그렇다면 우리가 할 일은 n을 구성하는 소수의 거듭제곱꼴에서 지수부분을 다 구하고

모든 지수들보다 크거나 같은 2^k 값중 가장 작은 k를 구한다.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
 
typedef long long ll;
 
ll p[1000001];
ll c[1000001];
vector<ll> primes;
vector<ll> s;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    ll n;
    cin >> n;
    primes.push_back(2);
    for (ll i = 3; i <= n; i += 2) {
        if (p[i]) continue;
        p[i] = 2;
        primes.push_back(i);
        for (ll j = i * i; j <= n; j += 2 * i)
            p[j] = 1;
    }
    ll temp = n;
    for (ll i = 0; i < primes.size() && primes[i] <= n; ++i) {
        while (temp && temp%primes[i] == 0) {
            c[primes[i]]++;
            temp /= primes[i];
        }
    }
    ll ans = 1;
    for (ll i = 1; i <= n; ++i) {
        if (c[i]) {
            ans *= i;
            s.push_back(c[i]);
        }
    }
    sort(s.begin(), s.end());
    cout << ans << " ";
    ll i = 1, cnt = 0;
    if (n == 1) {
        cout << 0;
        return 0;
    }
    for (; i < s[s.size() - 1]; i *= 2, cnt++);
    for (auto j : s) {
        if (j != i) {
            cout << cnt + 1;
            return 0;
        }
    }
    cout << cnt;
    return 0;
}