When the prime factorization of a positive integer \(K\) is \(K=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\), where \(p_1, p_2, \ldots,\) and \(p_m\) are distinct primes and \(a_1,a_2,\ldots, a_m\) are positive integers, an integer \(X\) is a multiple of \(K\) if and only if “for all \(1\leq i\leq m\), \(X\) is multiple of \(p_i^{a_i}\).” Also, if \(N<N'\), then \(N'!\) is a multiple of \(N!\).

Therefore, we can find the answer through the following three steps:

1. Factorize \(K\) into primes.
   
2. Find the minimum \(N_i\) such that \(N_i!\) is a multiple of \(p_i^{a_i}\) for each \(1\leq i\leq m\),
   where \(K=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\) is a prime factorization of \(K\).
3. The answer is found as \(N=\max(N_1,N_2, \ldots, N_m)\).

1. Factorize \(K\) into primes

A naive implementation is to check for each prime less than \(K\), count how many times it is divided by the prime. However, this does not finish in the time limit, because \(K\) can be at most \(10^{12}\) due to the Constraints, and there are more than \(10^{10}\) primes less than \(10^{12}\). Instead, we consider the following way.

\(K\) has at most one prime factor greater than \(\sqrt{K}\). Because, if \(K\) has two prime factors \(p\) and \(q\) such that \(p,q>\sqrt{K}\) and \(p\neq q\), then \(K\geq pq>K\), which is a contradiction. Therefore, when \(K\) is expressed as \(K=p_1^{a_1}p_2^{a_2}\cdots p_{m'}^{a_{m'}}\times M\) with different primes \(p_1, p_2, \ldots, p_m'\) less than \(\sqrt{K}\), positive integers \(a_1,a_2,\ldots, a_{m'}\), and an integer \(M\), then \(M\) is either \(1\) or a prime. This way, you can obtain the prime factorization of \(K\).

Regarding “how many times it divides,” since \(K=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\geq 2^{a_1+a_2+\cdots+a_m}\), the number of times each primes divides the integer, that is, the sum of \(a_i\) is at most \(\log_2 K\), so the complexity is \(O(\sqrt{K}+\log K)=O(\sqrt{K})\).

2. Find the minimum \(N_i\) such that \(N_i!\) is a multiple of \(p_i^{a_i}\)

For a prime \(p\) and a positive integer \(X\), let us define \(f_p(X)\) by the non-negative integer \(a\) such that \(X\) is a multiple of \(p^a\) but not of \(p^{a+1}\). What we seek is \(N_i\) such that \(f_{p_i}((N_i-1)!)<a_i\leq f_{p_i}(N_i!)\).

Since \(f_p(N'!)=f_p((N'-1)!)+f_p(N')\), it should hold that \(f_{p_i}(N_i)>0\), i.e. \(N_i\) should be a multiple of \(p_i\); also, \(N_i\leq a_ip_i\) obviously. Therefore, by computing \(f_{p_i}(p_i!)=1\) and \(f_{p_i}(N'!)=f_{p_i}((N'-p_i)!)+f_{p_i}(N')\) for each \(N'=p_i,2p_i, \ldots\) in this order, \(N_1,N_2,\ldots\), and \(N_m\) can be found in a total of \(O(\log K)\) time, since the sum of \(a_i\) is at most \(O(\log K)\).

We can obviously find \(N=\max(N_1,N_2, \ldots, N_m)\) from these values in an \(O(m)=O(\log K)\) time.

Therefore, the bottleneck is the prime factorization in step 1., and the problem has been solved in a total of \(O(\sqrt{K})\) time.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main() {
	long long k,p,a,n,x,ans=1;
	cin >> k;
	for(p=2;(p*p)<=k;p++){
		a=0;
		while(k%p==0)k /= p, a++;
		n=0;
		while(a>0){
			n+=p;
			x=n;
			while(x%p==0)x /= p,a--;
		}
		ans=max(ans,n);
	}
	ans=max(ans,k);
	cout << ans <<endl;
	return 0;
}