#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;
			}
		}
	}
}

• power(n,1.0/p) (2599) achilles 2005-10-08 20:34:53
  • Re:power(n,1.0/p) (46) cpp050400448168 2005-10-08 22:11:08