高精度計算對象
高精度加、減、單乘、雙乘、比較大小、讀入、輸出
#include <iostream>
using namespace std;
template<int LIM,int MAX> class hp
{
public:
//vars
int sect[MAX];
int scnt;
//constructors
hp()
{
scnt=1;
sect[0]=0;
}
//functions
void copy(const hp<LIM,MAX> &A)
{
for (int i=0;i<A.scnt;i++)
sect[i]=A.sect[i];
scnt=A.scnt;
}
void copy(int A)
{
scnt=0;
while (A)
{
sect[scnt++]=A % LIM;
A /=LIM;
}
}
void print()
{
int i,k;
printf("%d",sect[scnt-1]);
for (i=scnt-2;i>=0;i--)
{
k=LIM/10;
while(sect[i]<k)
{
printf("0");
k/=10;
}
if (sect[i])
printf("%d",sect[i]);
}
}
void read(int LIE)
{
char A[LIM*MAX];
int len,i,j,k,b=0;
scanf("%s",A);
len=strlen(A);
k=len % LIE;
j=scnt=len / LIE;
if (k)
{
scnt++;
j=scnt-1;
sect[j]=0;
for (i=0;i<k;i++)
{
sect[j]*=10;
sect[j]+=A[b++]-'0';
}
}
for (j--;j>=0;j--)
{
sect[j]=0;
for (i=0;i<LIE;i++)
{
sect[j]*=10;
sect[j]+=A[b++]-'0';
}
}
}
void plus(hp<LIM,MAX> &A,int offset=0)
{
int sc=scnt > A.scnt + offset ? scnt : A.scnt + offset;
int i,j,up=0;
for (i=0;i<sc;i++)
{
j=i - offset;
if (j<0) continue;
if (i>=scnt) sect[i]=0;
if (j>=A.scnt) A.sect[j]=0;
sect[i]+=A.sect[j] + up;
up=sect[i] / LIM;
sect[i]%=LIM;
}
scnt=sc;
if (up) sect[scnt++]=up;
}
void minus(hp<LIM,MAX> &A)
{
int sc=scnt;
int i,lend=0;
for (i=0;i<sc;i++)
{
if (i>=A.scnt) A.sect[i]=0;
sect[i]-=A.sect[i] + lend;
lend=0;
if (sect[i]<0)
{
lend=1;
sect[i]+=LIM;
}
}
scnt=sc;
if (lend) scnt--;
for (;scnt>1 && sect[scnt-1]==0;scnt--);
}
void multiply(int p)
{
if (p==0)
{
scnt=1;
sect[0]=0;
return;
}
int sc=scnt;
int i,up=0;
for (i=0;i<sc;i++)
{
if (i>=scnt) sect[i]=0;
sect[i]=sect[i] * p + up;
up=sect[i] / LIM;
sect[i]%=LIM;
}
scnt=sc;
if (up) sect[scnt++]=up;
}
void multiply(hp<LIM,MAX> &A)
{
hp<LIM,MAX> T,C;
int sc=A.scnt;
int i;
for (i=0;i<sc;i++)
{
T=(*this);
T.multiply(A.sect[i]);
C.plus(T,i);
}
scnt=sc;
(*this)=C;
}
int compare(hp<LIM,MAX> &A)
{
if (scnt > A.scnt)
return 1;
if (scnt < A.scnt)
return -1;
for (int i=scnt-1;i>=0;i--)
{
if (sect[i] > A.sect[i])
return 1;
if (sect[i] < A.sect[i])
return -1;
}
return 0;
}
//operators
bool operator == (hp<LIM,MAX> &A)
{
int t=compare(A);
return t==0;
}
bool operator < (hp<LIM,MAX> &A)
{
int t=compare(A);
return t==-1;
}
bool operator > (hp<LIM,MAX> &A)
{
int t=compare(A);
return t==1;
}
bool operator <= (hp<LIM,MAX> &A)
{
int t=compare(A);
return t==-1 || t==0;
}
bool operator >= (hp<LIM,MAX> &A)
{
int t=compare(A);
return t==1 || t==0;
}
void operator =(hp<LIM,MAX> A)
{
copy(A);
}
void operator =(int A)
{
copy(A);
}
void operator +=(hp<LIM,MAX> &A)
{
plus(A);
}
void operator -=(hp<LIM,MAX> &A)
{
minus(A);
}
void operator *=(hp<LIM,MAX> &A)
{
multiply(A);
}
void operator *=(int A)
{
multiply(A);
}
hp<LIM,MAX> operator +(hp<LIM,MAX> &A)
{
hp<LIM,MAX> C(*this);
C.plus(A);
return C;
}
hp<LIM,MAX> operator -(hp<LIM,MAX> &A)
{
hp<LIM,MAX> C(*this);
C.minus(A);
return C;
}
hp<LIM,MAX> operator *(int A)
{
hp<LIM,MAX> C(*this);
C.multiply(A);
return C;
}
hp<LIM,MAX> operator *(hp<LIM,MAX> &A)
{
hp<LIM,MAX> C(*this);
C.multiply(A);
return C;
}
};
typedef hp<10000,100> hpnum;
hpnum A,B;
hpnum qp(int P)
{
hpnum A;
if (P/2==1)
A=2;
else
A=qp(P/2);
A*=A;
if (P%2==1)
A*=2;
return A;
}
void mason()
{
int P;
B=1;
freopen("mason.in","r",stdin);
freopen("mason.out","w",stdout);
scanf("%d",&P);
A=qp(P);
A-=B;
A.print();
}
void mul()
{
char c;
hpnum A,B,C;
freopen("mul.in","r",stdin);
freopen("mul.out","w",stdout);
A.read(4);
while ((c=getchar())==10 || c==13);
ungetc(c,stdin);
B.read(4);
C=A*B;
C+=B;
C.print();
}
int main()
{
//mason();麥森數
//mul();高精度乘法例子
return 0;
}