> #include <iostream.h>
> #include <string.h>
> 
> #define N 1000
> 
> char result[1000];
> char *str;
> int itempresult[1000],iresult[1000],imid[10];
> int rlen,slen,irsize,itrsize,imsize,power,mid;
> int tool[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
> 
> void translate(int *cont,int size) //把cont里存的大整数转成字符串
> {
> 	rlen=0;
> 	int intIndex=size-1;
> 	int ntool,i,temp;
> 
> 	temp=cont[intIndex];
> 	if(temp>=100) ntool=3;
> 	else if(temp>=10) ntool=2;
> 	else ntool=1;
> 	for(i=ntool-1; i>=0; i--){
> 		result[rlen]=temp/tool[i]+'0';
> 		temp%=tool[i];
> 		rlen++;
> 	}
> 	intIndex--;
> 	while(intIndex>=0){
> 		temp=cont[intIndex];
> 		for(i=2; i>=0; i--){
> 			result[rlen]=temp/tool[i]+'0';
> 			temp%=tool[i];
> 			rlen++;
> 		}
> 		intIndex--;
> 	}
> 	result[rlen]=0;
> }
> 
> void calculate() //求mid的power次方
> {
> 	int temp=mid;
> 	int i,j,k;
> 	
> 	imsize=0;
> 	while(temp>=N){
> 		imid[imsize]=temp%N;
> 		imsize++;
> 		temp/=N;
> 	}
> 	imid[imsize]=temp;
> 	imsize++;
> 	
> 	for(i=0; i<imsize; i++){
> 		itempresult[i]=imid[i];
> 	}
> 	itrsize=imsize;
> 	irsize=0;
> 
> 	for(i=1; i<power; i++){
> 		for(j=0; j<irsize; j++){
> 			iresult[j]=0;
> 		}
> 		for(j=0; j<imsize; j++){
> 			for(k=0; k<itrsize; k++){
> 				iresult[j+k]+=imid[j]*itempresult[k];
> 			}
> 		}
> 		irsize=imsize+itrsize-1;
> 
> 		for(j=0; j<irsize; j++){
> 			if(iresult[j]>=N){
> 				iresult[j+1]+=iresult[j]/N;
> 				iresult[j]%=N;
> 			}
> 		}
> 		while( iresult[irsize]){
> 			iresult[irsize+1]=iresult[irsize]/N;
> 			iresult[irsize]%=N;
> 			irsize++;
> 		}
> 		if(i<power-1){
> 			for(j=0; j<irsize; j++){
> 				itempresult[j]=iresult[j];
> 			}
> 			itrsize=irsize;
> 		}
> 	}
> 	if(power==1) translate(itempresult,itrsize);
> 	else translate(iresult,irsize);
> 
> 	for(i=0; i<irsize; i++){
> 		iresult[i]=0;
> 	}
> }
> 
> void main()
> {
> 	int start,end;
> 	str=new char[200];
> 	
> 	while(cin>>power>>str){
> 		while(str[0]=='0') str++;
> 		slen=strlen(str);
> 
> 		start=1;
> 		end=2147483647;
> 		while( start<=end ){
> 			mid=start+(end-start)/2;
> 	//		cout<<start<<' '<<mid<<' '<<end<<endl;///
> 			calculate();
> 			
> 	//		cout<<"result:"<<result<<' '<<rlen<<endl;///
> 			if( rlen>slen ) end=mid-1;
> 			else if( rlen<slen ) start=mid+1;
> 			else{
> 				if(strcmp(result,str)==0 ){
> 					cout<<mid<<endl;
> 					break;
> 				}
> 				else if(strcmp(result,str)>0){
> 					end=mid-1;
> 				}
> 				else start=mid+1;
> 			}
> 		}
> 	}
> }

• Re:power(n,1.0/p) (46) cpp050400448168 2005-10-08 22:11:08