题目链接：http://codeforces.com/contest/1062/problem/B
题目大意：给你一个数n
你可以有两种操作
操作1：n等于n乘以一个正整数x
操作2：n=sqrt(n) 但是sqrt(n)必须为整数

问你n最后得到的最小值是多少？及其需要操作的最小步数

20*5=100， sqrt(100)=10

最小值为10， 操作步数为2

思路：
假如n能得到的最小值为a；

那么n · x一定是a的偶数次幂，n=a · a · a · a·…。2的幂次方个a相乘

那么把a分解质因数a=a1 · a2 · a3 · a4 · a5 · …。

那么n= 2的幂次方个a1 · 2的幂次方个a2 · 2的幂次方个 a3 ·…。

最小值就是a1 · a2 · a3 · a4 · a5 · …。

那么只要把n分解质因数，再找到出现次数多的质因数，那么次数就是
ceil(log2(m))+1

举例：n=48=2 · 2 · 2 · 3 · 3
m=3

所以：只能把n凑成 2 · 2 · 2 · 2 · 3 · 3 · 3 · 3 那么x=2 · 3 · 3=18
sqrt(n) = 2 · 2 · 3 · 3
sqrt(n) = 2 · 3
一共3步

因为n*x为第一步
后面开方的步数为ceil(log2(m))

所以总共的步数为 ceil(log2(m))+1
m=出现次数最多的质因数的次数

当然如果m=1，那么就已经是最小的值，0 步。

我这里优化了一下，如果sqrt(n)==整数，那么就n=sqrt(n)，一直处理到sqrt(n)！=整数。再进行上面的操作。

思考：第一次遇到分解质因数的题，很有意思

#include<bits/stdc++.h>

using namespace std;

int a[1000005];

int sq(long long n)//判断sqrt(n)是否为整数
{
    if(sqrt(n)-(long long)sqrt(n)<1e-6)
        return 1;
    else
        return 0;
}

long long p=0;
int Solve(long long n, long long &m)
{
    for(long long i=2; i*i<=n; i++)//分解质因数
    {
        while(n%i==0)
        {
            p=max(p, i);
            n/=i;
            a[i]++;
        }
    }
    if(n!=1)//判断是否是最后的质因数
    {
        p=max(p, n);
        a[n]++;
    }
    
    int s=1;
    for(int i=2;i<=p;i++)//计算最小值
    {
        if(a[i]!=0)
            s*=i;
    }
    
    /*计算次数*/
    m=*max_element(a, a+p+1);
    if(m==1)
        m=0;
    else
        m=ceil(log2(m))+1;

    return s;

}


int main()
{
    fill(a, a+1000005, 0);
    long long n, m, s=0;
    scanf("%lld",&n);
    if(n==1)
    {
        cout<<1<<' '<<0<<endl;
        return 0;
    }
    while(sq(n)&&n!=1)//处理sqrt(n)为整数
    {
        n=sqrt(n);
        s++;
    }
    int sum=Solve(n, m);
    cout<<sum<<' '<<m+s<<endl;


    return 0;
}