Posted on 2010-08-11 16:49
Onway 閱讀(1781)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
傷不起的ACM
pku 2109 一句話就能AC得題目？
這個(gè)題目的是求一個(gè)大整數(shù)p（10^101）開(kāi)n（1<=n<=200）次方的結(jié)果k，即k^n=p或者，n=log k (p).
題目說(shuō)保證p和n都是整數(shù)，并且求到得結(jié)果k一定是一個(gè)整數(shù)。但discuss里有說(shuō)，有些測(cè)試數(shù)據(jù)是不存在整數(shù)k的。
這個(gè)題目的本意應(yīng)該是高精度加二分吧，但我沒(méi)寫(xiě)。
在discuss看到，有些是直接用double和pow()函數(shù)的，一句話AC了以后，有很大的“罪惡感”。
本人小菜，連double和pow()都不會(huì)用，用了也是一頭霧水，覺(jué)得這種方法能通過(guò)，完全是因?yàn)闇y(cè)試數(shù)據(jù)太弱。
（在VC++ 6.0調(diào)試）
一句話能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接受一個(gè)10^101次方的數(shù)，確實(shí)可以，因?yàn)閐ouble的范圍是-1.7^308~1.7^308，但精度只有16或17位（四舍五入位）。
然后設(shè)p是一個(gè)大于17位的整數(shù)，那么四舍五入后可能得到的兩個(gè)值p1和p2，不妨記p1>p,p2<p。
就算測(cè)試數(shù)據(jù)都是合法的，就是說(shuō)能保證k是一個(gè)整數(shù)，即有k=p^(1/n)。那么可以保證的是p1^(1/n)>k而p2^(1/n)<k的。
那么問(wèn)題就來(lái)了，p1^(1/n)的上界怎么確定，p2^(1/n)的下界又怎么確定呢？
用double和pow()函數(shù)至少要能確保k+1>p1^(1/n)>k和k-1<p2^(1/n)<k吧？因?yàn)橹挥羞@樣，對(duì)結(jié)果pow(p,1/n)四舍五入才能得到結(jié)果k。
但如何能確保對(duì)p用double存儲(chǔ)的時(shí)候得到的估計(jì)值p1和p2的精確度在
p1-p<(k+1)^n-k^n和p-p2>k^n-(k-1)^n呢？
本人的智商只能到這里，還望各路神牛不吝賜教。