正整数 \(K\) が、異なる素数 \(p_1, p_2, \ldots, p_m\) および 正整数 \(a_1,a_2,\ldots, a_m\) を用いて \(K=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\) と素因数分解できる時、正整数 \(X\) が \(K\) の倍数であることは、「任意の \(1\leq i\leq m\) について、 \(X\) が \(p_i^{a_i}\) の倍数である 」ことと同値です。 また、\(N<N'\) のとき、\(N'!\) は \(N!\) の倍数となっています。

よって、次の \(3\) ステップによって、答えを求める事ができます。

1. \(K\) を素因数分解する。
   
2. \(K\) の素因数分解を \(K=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\) として,
   各 \(1\leq i\leq m\) について、\(N_i!\) が \(p_i^{a_i}\) の倍数となるような最小の \(N_i\) を求める。
3. \(N=\max(N_1,N_2, \ldots, N_m)\) として最終的な答えが求まる.

1. \(K\) を素因数分解する

ナイーブな実装方針としては、\(K\) 以下の各素数について、何度割り切れるかを確認するものが挙げられます。 しかし、\(K\) は制約より最大で \(10^{12}\) であり, \(10^{12}\) 以下の素数は \(10^{10}\) 個以上あるため、これは間に合いません。そこで次のような方法を考えます。

\(K\) は \(\sqrt{K}\) より大きい素因数を高々 \(1\) つしか持ちません。なぜなら、\(K\) が \(p,q>\sqrt{K}, p\neq q\) であるような素数 \(p,q\) を約数に持つとすると, \(K\geq pq>K\) となり、矛盾するからです。よって、 \(K\) を \(\sqrt{K}\) 以下の異なる素数 \(p_1, p_2, \ldots, p_m'\) 、正整数 \(a_1,a_2,\ldots, a_{m'}\) および 正整数 \(M\) を用いて、\(K=p_1^{a_1}p_2^{a_2}\cdots p_{m'}^{a_{m'}}\times M\) と表せるとすると、\(M\) は \(1\) または素数となります。このようにして、\(K\) の素因数分解を得る事ができます。

また、「何回割り切れるか」という部分については、\(K=p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\geq 2^{a_1+a_2+\cdots+a_m}\) より、各素数で何度割り切れるか, すなわち \(a_i\) の総和は高々 \(\log_2 K\) であることから、計算量は \(O(\sqrt{K}+\log K)=O(\sqrt{K})\) となります。

2. \(N_i!\) が \(p_i^{a_i}\) の倍数となるような最小の \(N_i\) を求める

素数 \(p\) と正整数 \(X\) について、\(X\) が \(p^a\)の倍数かつ\(p^{a+1}\) の倍数ではないような非負整数 \(a\) を\(f_p(X)\) として定義します。求めたいものは \(f_{p_i}((N_i-1)!)<a_i\leq f_{p_i}(N_i!)\)となるような \(N_i\) です。

\(f_p(N'!)=f_p((N'-1)!)+f_p(N')\) であることから \(f_{p_i}(N_i)>0\)、すなわち\(N_i\) は \(p_i\) の倍数である必要があり、また、明らかに \(N_i\leq a_ip_i\) です。 よって、\(N'=p_i,2p_i, \ldots\) について順に \(f_{p_i}(p_i!)=1\), \(f_{p_i}(N'!)=f_{p_i}((N'-p_i)!)+f_{p_i}(N')\) と計算したとすると、今、\(a_i\) の合計が 高々 \(O(\log K)\) であったことから, \(N_1,N_2,\ldots,N_m\) は全体で \(O(\log K)\) で求める事ができます。

これらから\(N=\max(N_1,N_2, \ldots, N_m)\)を求めることは明らかに \(O(m)=O(\log K)\) でできます。

よって、1. の素因数分解が計算量のボトルネックであり、全体で \(O(\sqrt{K})\) でこの問題を解く事ができました。

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;
}