题目大意:给你两个整数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; }