POJ2109 Power of Cryptography 二分

时间:2023-02-02 14:53:14

题目大意:给你两个整数n和p(1<=n<= 200, 1<=p<10101 ),让你找出一个整数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;
}