Codeforces Round #520 (Div. 2) B math（素数因子的应用）

给出一个n ;

有两个操作： 1，mul A , n=n*A ； 2，sqrt() , n=sqrt(n）开更出来必须是整数；

求出经过这些操作后得出的最小 n , 和最小操作数；

分析：首先得明确知道分解到怎样的时候才是得出最小的n , 首先进过手画就可以明明，经过分解n 可以发现它的素数因子是不可以被开根去的，无论怎么相乘开根的结果总是留在的，好那这到题的MIN(n) = (本身所有的素数因子的鸡) ；

那操作数怎么求呢？

首先我们只需要一次的相乘把它化简为完美状态（完美状态是指，所有的素数因子的个数相同）；

那剩下的直接开根就好，完美AC

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int n;

    scanf("%d",&n);

    if(n==)

    {

        printf("1 0\n");

        return ;

    }

    int MAX,MIN,W;

   MAX=;

   MIN=0x3f3f3f3f;

   W=;

   for(int i= ; i*i<=n ; i++)///找到素数因子

   {

       if(n%i==)

       {

           int cnt=;  ///记录当前素数因子的个数

           W*=i;       ///最终的为所有的素数因子的鸡

           while(n%i==)

           {

               n/=i;

               cnt++;

           }

           MAX=max(MAX,cnt);

           MIN=min(MIN,cnt);

           if(n==)

           break;

       }

   }

   if(n>)

   {

       MAX=max(MAX,);

       MIN=min(MIN,);

       W*=n;

   }

   printf("%d ",W);

   int num=;

   for(int i= ; i<= ; i++)

   {

       if((<<i) >=MAX)

       {

           int num=i;

           if(MIN==(<<i))

           {

           }

           else

            num++;///if最小因子的个数与最大的不一样就要进过乘机的运算了

           printf("%d",num);

           break;

       }

   }

}

巴特西

Codeforces Round #520 (Div. 2) B math（素数因子的应用）

最新文章

热门文章