AcWing 4486. 数字操作

给定一个整数 n n n，你可以对该数进行任意次（可以是 0 0 0 次）变换操作。

每次操作为以下两种之一：

• 将整数 n n n 乘以任意一个正整数 x x x。
• 将整数 n n n 替换为 n sqrt{n} n ​（执行此操作的前提是 n sqrt{n} n ​ 为整数）。

请你计算，通过上述操作， n n n 能达到的最小可能值，以及达到最小可能值所需要的最少操作次数。

一个整数 n n n。

一行，两个整数，分别为 n n n 能达到的最小可能值，以及达到最小可能值所需要的最少操作次数。

所有测试点满足 1 ≤ n ≤ 1 0 6 1 le n le 10^6 1≤n≤106。

20

10 2

5184

6 4

#include 
#include 
#include 
#include 

using namespace std;

const int MaxV=1E6+10;

int num,step;
int d[MaxV];                        //d[i]记录质因数i的指数

int Init()                          //先分解质因数
{
    int t=num,maxn=sqrt(t),maxc=-1;
    for(int i=2;i<=maxn;i++)
    {
        while(t%i==0)
        {
            t/=i;
            d[i]++;
            maxc=max(maxc,d[i]);
        }
    }
    if(t>1)
    {
        d[t]++;
        maxc=max(maxc,d[t]);
    }
    return maxc;                    //取所有因数的最大值
}

int main()
{
    int maxc;
    long long t=1;                  //记录所有质因数的乘积(不包括幂)
    cin>>num;
    maxc=Init();
    int i=0,sum2=0;
    while(maxc>pow(2,i))i++;        //寻找最小的2^n>=maxc
    int l=i;                        //记录结果
    for(int i=1;i<=num;i++)
    {
        if(d[i])
        {
            t*=i;                   //记录所有质因数的乘积
            sum2+=pow(2,l)-d[i];    //对(不用乘)的数字的特殊处理,即直接开根号
        }
    }
    if(sum2==0||i==0)               //特殊情况,直接开根号
    {
        cout< 
 
 
Thank you 
点个赞在走呗