首页 > 代码库 > nyist 773 开方数(大数问题)

nyist 773 开方数(大数问题)





开方数

时间限制:500 ms  |  内存限制:65535 KB
难度:3


描述
现在给你两个数 n 和 p ,让你求出 p 的开 n 次方。
输入
每组数据包含两个数n和p。当n和p都为0时表示输入结束。(1<=n<=200,1<=p<=10^101)
输出
对于每个输出对用输出开方后的结果k(结果小于10^9)。
样例输入
2 16
3 27
7 4357186184021382204544
0 0
样例输出
4
3
1234
上传者
TC_杨闯亮

这个题目出题者想要我们用二分查找或者是用牛顿迭代,却没想到直接用公式就可以做出来啊,公式水过~

pow()这个函数用法好多啊,转换一下思维就可以求开方了,比如 16的4分之一次方就等于 2,注意这个函数要是double浮点数,后面用分数的形式~

这个题如果用公式做用java就没什么优势啦~公式题还是用c/c++吧~;

c代码(公式法)

 
#include<stdio.h>
#include<math.h>
int main()
{
double n,p,x;
while(scanf("%lf%lf",&n,&p)!=EOF)
{
if(n==0&&p==0) return 0;
printf("%.lf\n",pow(p,1.0/n));
}
return 0;
}        

看了别人用二分法写的代码,效率也感觉也差不多~

 

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

int main()
{
    //freopen("Input.txt","r",stdin);
    //freopen("Output1.txt","w",stdout);
    long mid,left,right;
    double p;
    int n;
    while(~scanf("%d%lf",&n,&p)){
        if(n==0 && p==0.0) break;
        left=0,right=1000000000;
        while(left<right)
        {
            mid=(left+right)/2;
            if(pow(mid,n)==p) break;
            if(pow(mid,n)<p)left=mid;
            if(pow(mid,n)>p)
                right=mid;
        }
        //printf("%lf\n",p);
        printf("%ld\n",mid);
    }
    return 0;
}
                

下面是java写的代码:用时和内存都比c写的要多的多

package com.nyist;


import java.util.Scanner;

public class nyist773 {

	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		while(cin.hasNext())
		{
			 int n=cin.nextInt();  
			 double p=cin.nextDouble();  
			 if(n==0&&p==0)
				     break;
			 System.out.println(String.format("%.0f", Math.pow(p, 1.0/n)));  
		}
	}

}
最近两天大数题水的够多了,对java的大数类积累了一点知识吧,还是没达到那种熟练的地步,还是要不断的练习!!!