POJ 3100 Root of the Problem（我的水题之路——取A^N最接近B的A）-白红宇

POJ 3100 Root of the Problem（我的水题之路——取A^N最接近B的A）

阅读量：4069 次

发布时间：2019-05-25

本文共 1681 字，大约阅读时间需要 5 分钟。

Root of the Problem

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10067		Accepted: 5372

Description

Given positive integers B and N, find an integer A such that A^N is as close as possible to B. (The result A is an approximation to the Nth root of B.) Note that A^N may be less than, equal to, or greater than B.

Input

The input consists of one or more pairs of values for B and N. Each pair appears on a single line, delimited by a single space. A line specifying the value zero for both B and N marks the end of the input. The value of B will be in the range 1 to 1,000,000 (inclusive), and the value of N will be in the range 1 to 9 (inclusive).

Output

For each pair B and N in the input, output A as defined above on a line by itself.

Sample Input

4 35 327 3750 51000 52000 53000 51000000 50 0

Sample Output

123444516

Source

输入两个数字B和N。要求找一个A,使得A^N最接近B。

一开始想到的是暴力，不过想想或许可以换个方式来做这道题的。充分利用math.h里的pow()，先对B开n次方，就是用pow(b, 1.0/n).得到一个值right，然后分别对这个值取上整high和下整low，然后再计算pow(high,n)，pow(low, n)，比较这两个值中最小的那个就是答案。

注意点：

1）对B开方的时候，要使用浮点型被赋值。

2）如果n=1或者b=1的时候，直接输出b，算是优化吧。

代码（1AC）：

#include 
    
     #include 
     
      #include 
      
       int main(void){    int min, tmp;    int n, b;    float right;    int low, high;    while (scanf("%d%d", &b, &n), n != 0 || b != 0){        if (n == 1 || b == 1){            printf("%d\n", b);            continue;        }        right = pow(b, 1.0 / n);        low = (int)right;        high = (int)(right + 0.9999);        min = b - pow(low, n);        tmp = pow(high, n) - b;        if (tmp < min){            printf("%d\n", high);        }        else{            printf("%d\n", low);        }    }    return 0;}

代码（1AC）：

转载地址：http://ploji.baihongyu.com/

你可能感兴趣的文章