Dayi Lin, Ph.D.

Staff Researcher, AI & Software Engineering

POJ-2109 解题报告

POJ

题意简述

设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的返回值,在多个参数时,是返回成功赋值的参数个数。 这个很有用~

程序样例

#include<stdio.h>
#include<math.h>

int main() {
  double n, p;
  while (scanf("%lf%lf", & n, & p) == 2) {
    printf("%.0lf\n", pow(p, 1 / n));
  }
  return 0;
}

Leave a Reply

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