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

时间:2023-11-23 18:43:02

题意:

给出一个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;
}
}
}