POJ-2109 解题报告

题意简述

设k^n=p,给定n与p(1<=n<= 200, 1<=p<10^101),求k。输入数据保证存在k且1<=k<=10^9。

算法分析

这题乍看是用高精度,可是考虑到1s出解的时间限制,和数据规模,联想到神奇的double类型,就通啦~

这个数据规模,用double是完全存的下的。只需考虑如何求方根。

一种显而易见的方法:k=pow(p,1/n)。

这种方法直接就可以AC啦。

Problem Status: AC。时间0ms,内存136k

——————————————————————分割线——————————————————————

不过如果考虑不允许使用pow函数呢?

我们知道,k=p开n次方根。即:k=(e^(ln p))^(1/n)

即:k=e^(ln(p)/n)

所以也可以直接写成:k=exp(log(p)/n)

——————————————————————分割线——————————————————————

如果考虑不使用math库呢?在1s的情况下,二分法也好像会TLE。没有想到更好的解决方法。

——————————————————————分割线——————————————————————

TIPS:

题目中并没有说明如何判断停止读入数据。数据又有多组。这种情况直接用while(1)会出现OLE的情况。(人生中第一次看到神奇的OLE啊~)

可以使用:while(scanf(“%lf%lf”,&n,&p)==2)

scanf的返回值,在多个参数时,是返回成功赋值的参数个数。 这个很有用~

程序样例

[c]
#include&lt;stdio.h&gt;
#include&lt;math.h&gt;
int main()
{
double n,p;
while(scanf("%lf%lf",&n,&p)==2)
{
printf("%.0lfn",pow(p,1/n));
}
return 0;
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *