poj 2109 Power of Cryptography

今天懒了，这道题直接去看了大家的帖子，三行搞定。。。

题目大意： K ^ N = P, 给N 和 P， 求K。数据规模 ：1<=n<= 200, 1<=p<10101 and there exists an integer k, 1<=k<=109 。

看到1<=p<10¹⁰¹ 我就去想大数操作了，后来发现原来double完全可以放。

类型          长度 (bit)           有效数字          绝对值范围
float             32                      6~7                  10^(-37) ~ 10^38
double          64                     15~16               10^(-307) ~10^308
long double   128                   18~19                10^(-4931) ~ 10 ^ 4932

接下来就是直接用pow(n,1/p)就可以了，这个也可以开方。

一般思路：二分+高精度算法

但是本题还有一个更加巧妙的办法去处理：

首先需要明确：double类型虽然能表示10^(-307)   ~   10^308, （远大于题意的1<=p<10¹⁰¹这个范围）,但只能精确前16位，因此必须慎用！

那么为了避免double对输入的数在运算过程中进行精确，那么我们必须让double的运算第一步就得到一个int（即小数点尾数全为0），这个不难理解。

然后根据题意，是求指数k，一般人自然想到利用 对数log，即k=log_np。但是不要忘记使用对数最大的问题就是没有log_np函数，只有log()函数（底数为e），为此要计算log_np就必须使用换底公式log_np=log(p)/log(n),即k= log(p)/log(n)，由于这使得double的运算变为了3次，而且执行除法前的两次对数运算log的结果未必都是int，很显然k是一个被精确了的double

很多人到这里就放弃了使用double，转换方向到正常思路（二分+高精度算法），但是不要忘记求指数k除了使用对数log，还能使用指数的倒数开n次方，这时就可以用pow函数了

k=pow(p,1.0/n)，double的运算一步到位，k自然也是一个int

#include<iostream>
#include<math.h>

using namespace std;

int main(void)
{
	double n,p;

	while(cin>>n>>p)
		cout<<pow(p,1.0/n)<<endl;  //指数的倒数就是开n次方

	return 0;
}

还看到一种二分法，由p最大值最小值的中间值开始猜k，通过比较pow(k,n)与p的大小来进一步精确k，直到找到。