POJ2109 Power of Cryptography 二分

题目大意：给你两个整数n和p（1<=n<= 200, 1<=p<10¹⁰¹ ），让你找出一个整数k，使n^k=p。

分析：

有两种思路：

（1）看一下就可以知道，p的范围是可以用double装下的。然后我们都知道pow函数可以计算一个数的n次方，那么开平方就是计算出一个数的1/n次方了。

实现代码：

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    double n,p,k;
    while(cin>>n>>p)
    {
        k=pow(p*1.0,1.0/n);
        printf("%.0lf\n",k);
    }
    return 0;
}

（2）再者就是二分了，因为k的范围题中给出的有，我们就每一次拿mid=（left+right）/2来不断逼近最终的k值。

实现代码：

#include <cstdio>
#include <iostream>
#include <cmath>
#define MAX 1000000001
using namespace std;
int main()
{
    double n,p,k;
    while(cin>>n>>p)
    {
        long long left=0,right=MAX;
        while(left<=right)
        {
            long long mid=(left+right)/2;
            if(pow(mid*1.0,n)==p)
            {
                printf("%lld\n",mid);
                break;
            }
            if(pow(mid*1.0,n)<p)
              left=mid;
            if(pow(mid*1.0,n)>p)
              right=mid;
        }
    }
    return 0;
}