自搬

原文

---

题面良心地给了翻译。

有乘法，有开方，显然与素因数分解有关。设 $n=\prod p_i^{a_i}$（$p_i$ 为素数，$a_i$ 为正整数），那么要使值最小，就要尽量开方。$p_i$ 都是素数，当然没有办法进一步开方。开方的本质是将每一个指数 $a_i$ 除以 $2$，那么令所有 $a_i$ 均为 $2^k$（$k$ 为正整数）时，可以进行 $k$ 次开方操作，使 $n=\prod p_i$，值最小。因此第一问的答案即为 $n=\prod p_i$。

第二问中，我们如何令 $n=\prod (p_i)^{2^k}$？显然，将 $n$ 乘上 $\prod (p_i)^{(2^k-a_i)}$ 即可。因此，乘法最多进行一次，因为当乘数为 $1$ 时可以不进行乘法。然后进行 $k$ 次开方。那么要让总操作次数最小，就要让 $k$ 尽量小。但又注意到 $k$ 还需满足 $2^k-(\max a_i) \geq 0$。我们解这个不等式得 $k\geq \log_2 (\max a_i)$，即最小整数解为 $k=\lceil\log_2 (\max a_i)\rceil$。第二问的答案也呼之欲出。

---

细节：

1. 要特判 $1$。上面的讨论都自动排除了 $1$ 这种特殊情况。
2. 仔细思考什么时候不用进行乘法操作。

#include <cstdio>
#include <cmath>
using namespace std;

int times[1000005];

int main(){
	int n,nn;
	scanf("%d",&n);
	if(n==1){
		printf("1 0");
		return 0;
	}
	int maxtm=0,tmcnt=0;
	nn=n;
	for(int i=2;i<=n;i++){
		while(!(nn%i)){
			nn/=i;
			times[i]++;
		}
		if(times[i]>maxtm)maxtm=times[i];
	}
	for(int i=2;i<=n;i++)
		if(times[i]<maxtm&&times[i])
			tmcnt++;
	if(maxtm==1){
		printf("%d 0",n);
	}else{
		int ans1=1;
		for(int i=2;i<=n;i++)
			if(times[i])
				ans1*=i;
		int ans2=ceil(log2(maxtm));
		if(pow(2,ans2)!=maxtm||tmcnt) ans2++;
//		printf("[Debug]%d %d\n",maxtm,tmcnt);
		printf("%d %d",ans1,ans2);
	}
	
	return 0;
}