题目大意：给出n和p，计算p的n次根方。数据范围：1<=n<=200，1<=p<=10的101次方
解题过程：
思路一：高精度加二分。在UVA上一直是WA，但怎么检查都没出错，后来去网上看了一位仁兄说高精度的在POJ能过，UVA过不了，我就去POJ试了。。居然真的过了。。。。
若是哪位看官用高精度在UVA过了，请赐教，将代码粘给我膜拜一下。
以下是我设计的数据和代码，有几个数据超过了范围，不过我设置的数组长是500，也能计算
设计数据：
1 1 1 999999989000000054999999835000000329999999538000000461999999670000000164999999945000000010999999999 2 16 3 27 7 4357186184021382204544 7 4381962969567270546875 7 4431879027673573392733 200 265613988875874769338781322035779626829233452653394495974574961739092490901302182994384699044001 25 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 100 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 25 975297712597046620379535289307795104154133281893905522953117352299700024999 25 9975029977012644688770519408137073518314311997800145707314442866847306822905312873502299970000249999 101 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 12 999999988000000065999999780000000494999999208000000923999999208000000494999999780000000065999999988000000001 11 999999989000000054999999835000000329999999538000000461999999670000000164999999945000000010999999999
代码：
# include <cstdio> # include <cstdlib> # include <ctime> # include <cmath> # include <iostream> # include <fstream> # include <cstring> # include <string> # include <sstream> # define maxint 2147483647 # define maxlen 500 //* #define fin cin #define fout cout //*/ using namespace std; /* ifstream fin("in.txt"); ofstream fout("out.txt"); //*/ struct bign{ int len; int s[maxlen]; bign(){ len=1; memset(s,0,sizeof(s)); } bign operator = (const char* num){ memset(s,0,sizeof(s)); len=strlen(num); for(int i=0;i<len;i++){ s[i]=num[len-1-i]-'0'; } return *this; } bign operator = (int num){ char s[maxlen]; sprintf(s,"%d",num); * this=s; return * this; } bign(const char* num){ *this=num; } bign(int num){ * this=num; } string str() const{ string res=""; for(int i=0;i<len;i++){ res=(char)(s[i]+'0')+res; } if(res=="") res="0"; return res; } bign operator + (bign b){ bign c; c.len=0; for(int i=0,g=0;g||i<max(len,b.len);i++){ int x=s[i]+b.s[i]+g; c.s[c.len++]=x%10; g=x/10; } return c; } bign operator * (bign b){ bign c=0; bign * result=new bign[len]; for(int i=0;i<len;i++){ memset(result[i].s,0,sizeof(result[i].s)); result[i].len=i; for(int j=0,g=0;g||j<b.len;j++){ int x=s[i]*b.s[j]+g; result[i].s[result[i].len++]=x%10; g=x/10; } c=c+result[i]; } for(int i=c.len-1;i>=0;i--){ // fout<<"在乘法中："<<c.str()<<endl; if(c.s[i]!=0) break; if(c.s[i]==0) c.len--; } return c; } int issame(bign b){ // fout<<"带比较： "<<str()<<" "<<b.str()<<" len:"<<len<<" "<<b.len<<endl; if(len<b.len) return -1; if(len>b.len) return 1; for(int i=len-1;i>=0;i--){ if(s[i]<b.s[i]) return -1; if(s[i]>b.s[i]) return 1; } return 0; } bign pow(int n){ bign res=1; for(int i=1;i<=n;i++){ res=res*(*this); } return res; } }; int judge(char* p,int ints){ char s[102]; sprintf(s,"%d",ints); if(strlen(p)>strlen(s)) return 1; if(strlen(p)<strlen(s)) return -1; for(int i=0;i<strlen(p);i++){ if(p[i]-s[i]>0) return 1; if(p[i]-s[i]<0) return -1; } return 0; } int main() { int n,k; int a,b; int c,d; /* cin>>c>>d; bign bd=d; bign r=bd.pow(c); fout<< r.str()<<endl; //*/ char p[102]; while(fin>>n>>p){ if(n==1) fout<<p<<endl; else if(strcmp(p,"1")==0) fout<<p<<endl; else{ a=(strlen(p)-1)/n; b=ceil((double)(strlen(p))/n); int begin=(int)pow((double)10,a); int end=(int)pow((double)10,b); // fout<<"begin:"<<begin<<" "<<"end:"<<end<<endl; if(judge(p,maxint)<1){//in int // fout<<"in int"<<endl; for(int i=begin;i<end;i++){ int res=(int)pow((double)i,n); if(judge(p,res)==0){ fout<<i<<endl; break; } } } else{ // fout<<"out of int"<<endl; bign bp=p; int low=begin; int high=end; ///* int mid=(low+high)/2; // fout<<"low:"<<low<<" high:"<<high<<" mid:"<<mid<<endl; bool isfound=false; while(high-low>1){ // fout<<"low:"<<low<<" high:"<<high<<" mid:"<<mid<<endl; bign bm=mid; int res=bp.issame(bm.pow(n)); if(res>0){ // fout<<"update low="<<mid<<endl; low=mid; } else if(res<0){ // fout<<"update high="<<mid<<endl; high=mid; } else{ fout<<bm.str()<<endl; isfound=true; break; } bm=high; res=bp.issame(bm.pow(n)); if(res==0){ fout<<high<<endl; break; } bm=low; res=bp.issame(bm.pow(n)); if(res==0){ fout<<low<<endl; break; } mid=(low+high)/2; } //*/ if(!isfound){ bign bm=high; int res=bp.issame(bm.pow(n)); if(res==0){ fout<<high<<endl; } else{ fout<<low<<endl; } } } } } return 0; }思路二：用double型，直接计算
虽然知道这道题的范围在double以内，一开始却没考虑用double，因为我觉得double不准确，后来看了网上分析才明白，这道题的数据很巧妙，k和k+1的n次方之差，是大于double的误差的。例如:
4332529576639313702577//1233的7次方
4357186184021382204544//1234的7次方 4381962969567270546875//1235的7次方 4431879027673573392733//1237的7次方。
而直接用double输入4357186184021382204544（1234的7次方）得到的结果是：4357186184021382004736，虽然小于正确值，却比1233的7次方大多了，所以可以直接用double做。
int main(){ double n; char p[200]; while(scanf("%lf%s",&n,p)==2){ double dp=atof(p); printf("%lf\n",dp); int k=pow(dp,1/n)+0.5; printf("%d\n",k); } return 0; } //*/ //* int main() { double n, p; while (scanf("%lf%lf", &n, &p) != EOF) { printf("%lf\n",p); printf("%.lf\n", pow(p, 1/n)); } return 0; } //*/两段代码在UVA上都AC注：学会一个新函数 atof(char* p)，可以将字符数组转化为double
不过对于double的精度来说没什么用，因为存起来的还是4357186184021382004736
