Posted on 2010-08-11 16:49
Onway 阅读(1765)
评论(2) 编辑 收藏 引用 所属分类:
伤不起的ACM
pku 2109 一句话就能AC得题目？
这个题目的是求一个大整数p（10^101）开n（1<=n<=200）次方的结果k，即k^n=p或者，n=log k (p).
题目说保证p和n都是整数，并且求到得结果k一定是一个整数。但discuss里有说，有些测试数据是不存在整数k的。
这个题目的本意应该是高精度加二分吧，但我没写。
在discuss看到，有些是直接用double和pow()函数的，一句话AC了以后，有很大的“罪恶感”。
本人小菜，连double和pow()都不会用，用了也是一头雾水，觉得这种方法能通过，完全是因为测试数据太弱。
（在VC++ 6.0调试）
一句话能AC的C代码是这样的：
#include <stdio.h>
#include <math.h>
void main()
{
double n,p;
while(scanf("%lf%lf",&n,&p)!=EOF)
printf("%.0f\n",pow(p,1/n));
}
首先用double接受一个10^101次方的数，确实可以，因为double的范围是-1.7^308~1.7^308，但精度只有16或17位（四舍五入位）。
然后设p是一个大于17位的整数，那么四舍五入后可能得到的两个值p1和p2，不妨记p1>p,p2<p。
就算测试数据都是合法的，就是说能保证k是一个整数，即有k=p^(1/n)。那么可以保证的是p1^(1/n)>k而p2^(1/n)<k的。
那么问题就来了，p1^(1/n)的上界怎么确定，p2^(1/n)的下界又怎么确定呢？
用double和pow()函数至少要能确保k+1>p1^(1/n)>k和k-1<p2^(1/n)<k吧？因为只有这样，对结果pow(p,1/n)四舍五入才能得到结果k。
但如何能确保对p用double存储的时候得到的估计值p1和p2的精确度在
p1-p<(k+1)^n-k^n和p-p2>k^n-(k-1)^n呢？
本人的智商只能到这里，还望各路神牛不吝赐教。