题解：CF1062B Math

· · 题解

题面良心地给了翻译。

有乘法，有开方，显然与素因数分解有关。设 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;

}