链接

[http://codeforces.com/contest/1062/problem/B]

题意

给你n,有两种操作要么乘以某个数，要么开根但必须开根后是整数才能开，问你最后能变成最小的数是多少，并输出步数

分析

就是唯一分解定理的应用，以及判断一个是数是否是2的幂次

还有log2取整的写法

详解链接

[https://blog.csdn.net/Hackbuteer1/article/details/6681157]

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll a[100000];

ll log2(ll value)   //递归判断一个数是2的多少次方

{

	if (value == 1)

		return 0;

	else

		return 1+log2(value>>1);

}

int main(){

    ll n,i;

    ios::sync_with_stdio(false);

    cin. tie(0);cout.tie(0);

    while(cin>>n){

        ll c=0;

        ll k=n;

        ll b[1000];

        int cnt=0;

        int j=0;

        for(i=2;i<=n;i++){

        	cnt=0;

            while(n%i==0){

                a[c++]=i;

                n/=i;

                cnt++;

            }

           if(cnt) b[j++]=cnt;

           cnt=0;

        }

        ll ans=1;

        a[c]=1000007;

        for(i=0;i<c;i++)

        if(a[i]!=a[i+1])

        ans=ans*a[i];

        sort(b,b+j);

        cnt=0;

        if(b[0]!=b[j-1]) cnt+=1;

        if(b[j-1]==1){

        	cout<<k<<' '<<0<<endl;

			return 0;

		}

		else if((b[j-1]&b[j-1]-1)==0) {//判断是否是2的幂次

			cout<<ans<<' '<<log2(b[j-1])+cnt<<endl;

		}

		else

           cout<<ans<<' '<<log2(b[j-1])+2<<endl;

    }

    return 0;

}