1062B. Math

Mathematics Number Theory Greedy

JATC’s math teacher always gives the class some interesting math problems so that they don’t get bored. Today the problem is as follows. Given an integer $𝑛$, you can perform the following operations zero or more times:

$\bullet mul 𝑥$: multiplies $𝑛$ by $𝑥$ (where $𝑥$ is an arbitrary positive integer).

$\bullet sqrt$: replaces $𝑛$ with $\sqrt 𝑛$ (to apply this operation, $\sqrt 𝑛$ must be an integer).

You can perform these operations as many times as you like. What is the minimum value of $𝑛$, that can be achieved and what is the minimum number of operations, to achieve that minimum value?

Apparently, no one in the class knows the answer to this problem, maybe you can help them?

Read the question with I/O specifications at codeforces.com.

Hints

Hint 1

Can you reduce a number through multiplication and square root operations beyond the product of its prime factors?

Hint 2

A number has an integral square root if it’s prime factor powers are even.

Solution

A number $n$ has an integral root when all the powers of the prime factors of $n$ are even.

For example, let $n = a^{x} \cdot b^{y}$

The root of the number, $\sqrt(n) = a^{x/2} \cdot b^{y/2}$

In this case, for the root to be integral, $x$ and $y$ must be even.

Since $n$ can be multiplied by any integer $x$, it can be taken to a position such that the end result, after multiple root operations, will be the product of all its prime factors - in this case, $a \cdot b$.

To reduce to the product of the primes - the minimum possible number, $n$ should be multiplied by a number $k$. Then performing the sqrt operation multiple times will result in the desired product. This will take the minimum number of steps as it is a one time multiplication followed by direct multiple sqrt operations.

$n \cdot k$ should be the smallest number greater than $n$ with all prime factor powers equal and a power of two. Multiplication by $n$ is not required if the the prime factor powers of $n$ are all equal to the same power of 2.

The total steps required, thus, is equal to $s$, if all the powers of prime factors are equal to $2^{s}$, else $s + 1$, with one being the $multi$ step to make all powers of prime factors equal to $2^{s}$. $s$ can be calculated by $\lceil \log_2 u \rceil$, where $u$ is the largest power in prime factorisation of n. And the lowest number will be equal to the product of the prime factors.

Code

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;

int isPowerOfTwo(ll x) {
    if(x && (!(x&(x-1)))) return 0;
    return 1;
} 

vector<int> pr;
void SieveOfEratosthenes(int n){
    vector<bool> prime(n+1,true);
    for (ll p=2; p*p <= n; p++) if (prime[p] == true) for (ll i=p*2; i<=n; i += p) prime[i] = false;
    for (int p=2; p<=n; p++) if (prime[p]) pr.pb(p);
}

int main() {

    int n;
    cin >> n;
    
    SieveOfEratosthenes(n);
    
    ll ans = 1;
    
    map<ll,ll> m;
    
    for(int i = 0 ; i < pr.size() && n; ++i) {
        if(n % pr[i] == 0){
            m[pr[i]]++;
            n /= pr[i];
            i--;
        }
    }
   
    ll steps = 0;
    for(auto it = m.begin(); it!=m.end(); ++it){
        ans *= it->ff;
        steps = max(steps, it->ss);
    }
    bool flag = 0;
    for(auto it = m.begin(); it!=m.end(); ++it){
        if(it->ss != steps){
            flag = 1;
            break;
        }
    }

    int temp = 0;
    if(flag) temp = 1;
    else temp = isPowerOfTwo(steps);
    if(steps == 1) steps--;
    else if(steps != 0) steps = ceil(log2(steps)) + temp;
    cout << ans << " " << steps << endl;
}

Written by Nandakishore