cata.cpp

高精度整数问题

#include<fstream>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<iomanip>
#include<math.h>
#include<time.h>
using namespace std;
const maxUnitVal=10000;   //大整数数组每个数组的最大整数值
const width=log10(maxUnitVal);
const charlength=5000;   //大整数数组的最大长度
const t=9;




bool compareInitial(int k1,int k2)  //判断k1,k2的最高位大小，如果k1最高位大于k2最高位返回true,否则返回false
{
	int m,n;
	int s=1,t=1;
	
	m=(int)log10(k1);  //m为k1的位数-1
	n=(int)log10(k2);  //n为k2的位数-1
	for(int i=0;i<m;i++)
		s*=10;
	for(i=0;i<n;i++)
		t*=10;
    m=k1/s;
	n=k2/t;

	while(s&&t)
	{
		if(m>n)
			return true;
		if(m<n)
			return false;
		else
		{
			k1%=s;
	        k2%=t;
			s/=10;
			t/=10;
			if(s>0)
				m=k1/s;
			if(t>0)			
				n=k2/t;
		}
	}
	return false;
}

/*/////////////////////////////////////////////////////
大数类方法包括：
        构造函数，
		加，减，乘，除
*//////////////////////////////////////////////////////
class	bignum{
public:
		bignum();
		bignum(int length,int* kk);
		bignum operator + (bignum&);
		bignum operator - (bignum&);
		bignum operator * (bignum&);
		bignum operator * (int);
		bignum operator / (bignum&);
		bignum operator % (bignum&);
		bool operator >= (const bignum&);
public:
        //bignum inttobig(int kk);
		//bignum strtobig(string str);

		//void output();

//private:
		int num[charlength];
		int	length;
};

bignum::bignum()
{			
	bignum::length=1;
	for(int i=0;i<charlength;i++)
    	bignum::num[i]=0;
}
bignum::bignum(int length,int* kk)
{
			
	bignum::length=length;			
	for(int i=0;i<length;i++)			
		bignum::num[i]=kk[i];						
}

bignum YuShu=bignum();//yushu是余数，它是求商的附属品，是一个全局变量

bool bignum::operator >= (const bignum& x)
{
	if (length>x.length)
		return true;
	if (length<x.length)
		return false;
	else
	{
		int k=length-1;
		while(k>0)
		{
    		if(num[k]>x.num[k])
			    return true;
	    	if(num[k]<x.num[k])
	    		return false;
			--k;
		}
        if(num[k]>=x.num[k])			  
			return true;
		else return false;
	}

}

bignum bignum::operator + (bignum& bigN)  //大整数加法运算 big+big
{
    int arr[charlength];
	int len=length;
	
	int k1,k2;
	int sum,inc;
	k1=len;

	k2=bigN.length;
	inc=0;

	if (k1<=k2)
	{	 
		for(int i=0;i<k1;i++)
		{
    		sum=num[i]+bigN.num[i]+inc;
	    	inc=sum / maxUnitVal;	    		
			arr[i]=sum % maxUnitVal;
		}
    	for( i=k1;i<k2;i++)
		{
	    	sum=bigN.num[i]+inc;
	    	inc=sum / maxUnitVal;
			arr[i]=sum % maxUnitVal;
		}
        while(inc!=0)
		{
    		arr[k2]=inc%maxUnitVal;
	        inc/=maxUnitVal;	
    		++k2;
		}
		len=k2;
	}

	if (k1>k2)
	{	 
		for(int i=0;i<k2;i++)
		{
    		sum=num[i]+bigN.num[i]+inc;
	    	inc=sum / maxUnitVal;
			arr[i]=sum % maxUnitVal;
		}
    	for( i=k2;i<k1;i++)
		{
	    	sum=num[i]+inc;
	    	inc=sum / maxUnitVal;
			arr[i]=sum % maxUnitVal;
		}
        while(inc!=0)
		{
    		arr[len]=inc%maxUnitVal;
	        inc/=maxUnitVal;	
    		++len;
		}
	}
    bignum bnum(len,arr);
	return bnum;

}

bignum bignum::operator - (bignum& bigN)  //大整数减法运算 big-big
{
    int arr[charlength];
	for(int i=0;i<length;i++)
		arr[i]=num[i];
	int len=length;
	bignum bnum=bignum(len,arr);

	int sum;
	int k1=len;
	int k2=bigN.length;
	int inc=0;  //借位


	if (bnum>=bigN)
	{	 
		for(int i=0;i<k2;i++)
		{
			sum=num[i]-inc-bigN.num[i];
			if(sum>=0)
			{				
				arr[i]=sum;
				inc=0;
			}
			else
			{
				sum+=maxUnitVal;
				arr[i]=sum;
				inc=1;
			}

		}
		while((inc)&&(k2<k1))
		{
			sum=num[k2]-inc;
			if(sum>=0)
			{				
				arr[k2]=sum;
				inc=0;
			}
			else
			{
				sum+=maxUnitVal;
				arr[k2]=sum;
				inc=1;
			}	
			++k2;		
		}

    	for( i=k2;i<k1;i++)
		{
			arr[i]=num[i];
		}

	}
    
    while((arr[--len]==0)&&(len>0));
		
    ++len;
    bnum=bignum(len,arr);
	return bnum;


}



bignum bignum::operator * (int num1)       //大整数乘法运算 big×int
{	
	//bignum bInt=bignum();
    
    int arr[charlength];
	int len=length;

	int kk;
	int inc=0;   //进位
	for(int i=0;i<len;i++)
	{
		kk=num[i];
		inc+=kk*num1;
		arr[i]=inc%maxUnitVal;
	    inc/=maxUnitVal;	
	}

    while(inc!=0)
	{
		arr[len]=inc%maxUnitVal;
	    inc/=maxUnitVal;	
		++len;
	}
    //num[length]=inc;

    bignum bnum(len,arr);
	return bnum;
}

bignum bignum::operator * (bignum& bigN)   //大整数乘法运算 big×big
{
	bignum bInt1=bignum();
    bignum bInt2=bignum();
	bignum bInt3=bignum();
	int pos=0;
	int k1,k2;
	for(int i=0;i<length;i++)
	{
		bInt2=bigN * num[i];
		k1=bInt1.length;
		k2=bInt2.length;
        int inc=0;
		int sum;
		for(int j=0;j<pos;j++)
		{
			bInt3.num[j]=bInt1.num[j];
		}

		if(k2>=k1-pos)
		{
	
			/*for(j=0;j<bInt1.length;j++)	
			{			
				bInt3.num[j+pos]=bInt1.num[j+pos]+bInt2.num[j];		
			}*/
			for(int k=0;k<bInt2.length;k++)
			{
				sum=bInt1.num[k+pos]+bInt2.num[k]+inc;
				bInt3.num[k+pos]=sum%maxUnitVal;
				inc=sum/maxUnitVal;
			}
	    	bInt3.length=bInt2.length+pos;
			if(inc)
			{
				bInt3.num[bInt3.length]=inc;
				++bInt3.length;
			}
			for(k=0;k<bInt3.length;k++)
			    bInt1.num[k]=bInt3.num[k];
			bInt1.length=bInt3.length;

		}
		if(k2<k1-pos)
		{
	
			for(j=0;j<bInt1.length-pos;j++)	
			{			
				bInt3.num[j+pos]=bInt1.num[j+pos]+bInt2.num[j];		
			}

			for(int k=0;k<bInt3.length;k++)
			    bInt1.num[k]=bInt3.num[k];
			bInt1.length=bInt3.length;
		}

		++pos;
	}



	//bignum bnum(length,num);
	return bInt1;
}


bignum inttobig(int kk)
{
    bignum bnum;
	int m=0;
	int k1=kk%maxUnitVal;

    kk/=maxUnitVal;
	while(kk)
	{
		bnum.num[m]=k1;
		k1=kk%maxUnitVal;
	    kk/=maxUnitVal;
		++m;
	}
	bnum.num[m]=k1;
	bnum.length=++m;
	return bnum;
}

bignum strtobig(string str)
{
	//int width=log10(maxUnitVal);
	int k1,k2,len=0;
    bignum bnum;
	int i;
    for(i=str.length()-1;i>(width-1);i-=width)
	{
		k2=i-width+1;
		k1=0;
		for(int k=0;k<width;k++)
		{
	    	k1*=10;
    		k1+=str[k2++]-'0';
		}
		bnum.num[len]=k1;
		++len;
	}

	k1=0;
    for(int k=0;k<=i;k++)
	{	  	
		k1*=10;		
		k1+=str[k]-'0';

	}
	bnum.num[len]=k1;
	++len;

    bnum.length=len;
	return bnum;

}



bignum bignum::operator / (bignum& bigN)   //大整数除法运算 big/big
{
	bignum bInt1=bignum();
	bignum bInt2=bignum();
    bInt1.length=length;
	for(int i=0;i<length;i++)
		bInt1.num[i]=num[i];

    bignum Shang=bignum();
	if(bInt1 >= bInt1)
	{
		int k1=(bInt1.length-1)*width+(int)log10(bInt1.num[bInt1.length-1]);	
		int k2=(bigN.length-1)*width+(int)log10(bigN.num[bigN.length-1]);				
        int k3=k1-k2-1;

		k1=bInt1.num[bInt1.length-1];
		k2=bigN.num[bigN.length-1];
        if (compareInitial(k1,k2))
			++k3;


		///////下面构造一个10的k3次方的大数//////
        Shang.length=k3/width+1;
        k1=k3%width;
		k2=1;
		for(i=0;i<k1;i++)
			k2*=10;
        Shang.num[Shang.length-1]=k2;
		////////////////////////////////////////
		bInt2=bigN*Shang;
		bInt1=bInt1-bInt2;

		while(bInt1 >= bigN)
		{
		
			int k1=(bInt1.length-1)*width+(int)log10(bInt1.num[bInt1.length-1]);		
			int k2=(bigN.length-1)*width+(int)log10(bigN.num[bigN.length-1]);		     
			int k3=k1-k2-1;	
			
	    	k1=bInt1.num[bInt1.length-1];
	    	k2=bigN.num[bigN.length-1];
            if (compareInitial(k1,k2))
		    	++k3;

			if(k3<0)
				break;
			///////下面构造一个10的k3次方的大数//////  
		
			bInt2.length=k3/width+1;  
			for(i=0;i<bInt2.length;i++)
				bInt2.num[i]=0;

			k1=k3%width;	
			k2=1;	
			for(i=0;i<k1;i++)
			k2*=10;       
			bInt2.num[bInt2.length-1]=k2;	
			////////////////////////////////////////
            Shang=Shang+bInt2;
			
			bInt2=bigN*bInt2;		
			bInt1=bInt1-bInt2;
		}
	
        int kk=0;
        while(bInt1 >= bigN)
		{
			bInt1 = bInt1-bigN;
			++kk;
		}
        Shang=Shang+inttobig(kk);
		YuShu=bInt1;

		return Shang;

		
	}
	else
		return Shang;


}





void output(bignum& bigN)
{

	ofstream fout("output.txt");
	int m1=bigN.length-1;
	//cout<<bigN.num[m1];
	fout<<bigN.num[m1];
	//cout<<setfill('0');
	for(int i=m1-1;i>=0;i--)		
	{	
		//cout<<setw(width)<<bigN.num[i];
	    int pp=(int)log10(bigN.num[i]);
		int n=width-pp-1;
		if (n)
		{
			for(int j=0;j<n;j++)
				fout<<0;
		}
		fout<<bigN.num[i];	
	}
    //cout<<endl;
}



bignum Cmn(int m,int n)
{
	bignum bigN1,bigN2;
	bigN1=inttobig(1);
	bigN2=inttobig(1);
	bignum bigN3=bignum();
	if (m>=2*n)
	{
		for(int i=m-n+1;i<=m;i++)
			bigN1=bigN1*i;

		for(i=2;i<=n;i++)
			bigN2=bigN2*i;
		bigN3=bigN1/bigN2;
		return 	bigN3;
	}
	else
		Cmn(m,m-n);

}


void main()
{

	bignum bigN1,bigN2;
	bignum bigN3=bignum();
	string str1,str2;
	ifstream fin("input.txt");
	fin >> str1 >> str2;
	//cout<<"num1="<<str1<<endl<<"num2="<<str2<<endl;



    bigN1=strtobig(str1);
    bigN2=strtobig(str2);
/*
	bigN3=bigN1+bigN2;
	cout<<"  和=";
	output(bigN3);

	bigN3=bigN1-bigN2;
	cout<<"  差=";
	output(bigN3);*/

	bigN3=bigN1*bigN2;
	cout<<"  乘=";
	output(bigN3);

/*
	bigN3=bigN1/bigN2;
	cout<<"  商=";
	output(bigN3);
	cout<<"余数=";
	output(YuShu);

/*
	int m,n;
	ifstream fin2("input.txt");
	fin2 >> m >> n;
	cout<<m<<endl<<n<<endl;

	bigN3=Cmn(m,n);
	cout<<"  商=";
	output(bigN3);
	cout<<"余数=";
	output(YuShu);



	bigN3=Cmn(2*m,m);
    bigN3=bigN3/inttobig(m+1);
	cout<<"  商=";
	output(bigN3);
	cout<<"余数=";
	output(YuShu);*/


}