标准整数(vector)
#include<math.h>#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<vector>
#define LL_MAX 100
using namespace std;
class LLong
{
private:
vector<long> a;
int m;
int cp;
private:
int LL_BJ(const LLong &B);
LLong Help_Add(const LLong &B);
LLong Help_Sub(const LLong &B);
void LL_Div01(const LLong &B,LLong &Q01,LLong &R01);
void LL_Div02(const LLong &B,LLong &Q02,LLong &R02);
void LL_Div03(const LLong &B,LLong &Q03,LLong &R03);
void LL_Div(const LLong &B,LLong &Q,LLong &R);
public:
LLong();
LLong(char *s);
LLong(long d);
~LLong()
{ ;}
void print();
long get_a(int n);
int get_m();
int get_cp();
public:
LLong operator+(const LLong &B);
LLong operator-(const LLong &B);
LLong operator*(const LLong &B);
LLong operator^(const LLong &B);
LLong operator%(const LLong &B);
LLong operator/(const LLong &B);
int operator==(const LLong &B);
int operator!=(const LLong &B);
int operator>(const LLong &B);
int operator>=(const LLong &B){return(*this>B||*this==B);}
int operator<(const LLong &B);
int operator<=(const LLong &B){return(*this<B||*this==B);}
};
int main()
{
LLong a("8848");
LLong b("4494");
a.print();
cout<<endl;
b.print();
cout<<endl;
(a+b).print();
cout<<endl;
((LLong)8-b).print();
cout<<endl;
(a*b).print();
cout<<endl;
(a*5).print();
cout<<endl;
(a/b).print();
cout<<endl;
(a%b).print();
cout<<endl;
(a^b).print();
cout<<endl;
a.print();
cout<<endl;
b.print();
cout<<endl;
if(a!=b)
cout<<"a!=b"<<endl;
if(a>=b)
cout<<"a>=b"<<endl;
if(a<=b)
cout<<"a<=b"<<endl;
if(a<b)
cout<<"a<b"<<endl;
else if(a==b)
cout<<"a==b"<<endl;
else
cout<<"a>b"<<endl;
return 0;
}
LLong::LLong()
{
a.resize(LL_MAX);
a=0;
m=0;
cp=0;
}
LLong::LLong(char *s)
{
int n,i,t;
a.resize(LL_MAX);
if(*s=='-')
{
cp=1;
n=-1;
}
else if(*s=='+')
{
cp=0;
n=-1;
}
else
{
cp=0;
n=0;
}
while(*s!='\0')
{
n++;
s++;
}
if(n%4==0)
{
n=n/4;
t=4;
}
else
{
t=n%4;
n=n/4+1;
}
if(n==0)
cout<<"Not have dat"<<endl;
if(n>LL_MAX)
a.resize(n);
m=n-1;
for(i=0;i<n-1;i++)
a=*(s-1-4*i)-48+(*(s-2-4*i)-48)*10+
(*(s-3-4*i)-48)*100+(*(s-4-4*i)-48)*1000;
a=0;
for(i=1;i<=t;i++)
a=a+(*(s-i-4*(n-1))-48)*(int)pow(10,i-1);
}
LLong::LLong(long d)
{
a.resize(LL_MAX);
if(d<0)
cp=1;
else
cp=0;
d=abs(d);
if(d<10000)
{
m=0;
a=d;
}
else if(d<100000000)
{
m=1;
a=d%10000;
d=(d-d%10000)/10000;
a=d%10000;
}
else
{
m=2;
a=d%10000;
d=(d-d%10000)/10000;
a=d%10000;
d=(d-d%10000)/10000;
a=d%10000;
}
}
void LLong::print()
{
long i,b;
char aa;
if(cp==1)
printf("-");
printf("%ld",a);
for(i=m-1;i>=0;i--)
{
b=a%10;
b=((a-b)/10)%10;
b=((a-b-b*10)/100)%10;
b=((a-b-b*10-b*100)/1000)%10;
aa=b+48;
aa=b+48;
aa=b+48;
aa=b+48;
printf("%c%c%c%c",aa,aa,aa,aa);
}
}
long LLong::get_a(int n)
{
if((n>m)||(n<0))
{
cout<<"溢出"<<endl;
return 0;
}
else
return a;
}
int LLong::get_cp()
{
return cp;
}
int LLong::get_m()
{
return m;
}
int LLong::LL_BJ(const LLong &B)
{
int i;
if(m>B.m)
return 1;
else if(m<B.m)
return -1;
else
{
for(i=m;i>=0;i--)
{
if(a>B.a)
return 1;
else if(a<B.a)
return -1;
}
return 0;
}
}
int LLong::operator==(const LLong &B)
{
if(cp!=B.cp)
return 0;
if(LL_BJ(B)==0)
return 1;
else
return 0;
}
int LLong::operator!=(const LLong &B)
{
if((LL_BJ(B)==0)&&(cp==B.cp))
return 0;
else
return 1;
}
int LLong::operator<(const LLong &B)
{
if(cp>B.cp)
return 1;
else if(cp<B.cp)
return 0;
else
{
if(((cp==0)&&(LL_BJ(B)==-1))||((cp==1)&&(LL_BJ(B)==1)))
return 1;
else
return 0;
}
}
int LLong::operator>(const LLong &B)
{
if(cp>B.cp)
return 0;
else if(cp<B.cp)
return 1;
else
{
if(((cp==0)&&(LL_BJ(B)==1))||((cp==1)&&(LL_BJ(B)==-1)))
return 1;
else
return 0;
}
}
LLong LLong::Help_Add(const LLong &B)
{
LLong D;
int i;
for(i=0;i<=m;i++)
{
if(i<=B.m)
{
if(i+2>LL_MAX)D.a.resize(i+2);
D.a=(D.a+a+B.a)/10000;
D.a=(D.a+a+B.a)%10000;
}
else
{
if(i+2>LL_MAX)D.a.resize(i+2);
D.a=(D.a+a)/10000;
D.a=(D.a+a)%10000;
}
}
if(D.a==0)
D.m=m;
else
D.m=m+1;
return D;
}
LLong LLong::Help_Sub(const LLong &B)
{
LLong D;
int i,y=0;
for(i=0;i<=m;i++)
{
if(i<=B.m)
{
if(a-y>=B.a)
{
if(i+1>LL_MAX)D.a.resize(i+1);
D.a=a-y-B.a;
y=0;
}
else
{
if(i+1>LL_MAX)D.a.resize(i+1);
D.a=10000+a-y-B.a;
y=1;
}
}
else
{
if(a-y>=0)
{
if(i+1>LL_MAX)D.a.resize(i+1);
D.a=a-y;
y=0;
}
else
{
if(i+1>LL_MAX)D.a.resize(i+1);
D.a=10000+a-y;
y=1;
}
}
}
for(i=m;i>=0;i--)
if(D.a!=0)
{
D.m=i;
break;
}
return D;
}
LLong LLong::operator+(const LLong &B)
{
LLong D,AA,BB=B;
if(m+1>LL_MAX)AA.a.resize(m+1);
for(int i=0;i<=m;i++)
AA.a=a;
AA.m=m;
AA.cp=cp;
if((LL_BJ(BB)==1)||(LL_BJ(BB)==0))
{
if(cp==B.cp)
{
D=Help_Add(BB);
D.cp=cp;
}
else if((cp==0)&&(B.cp==1))
{
D=Help_Sub(BB);
D.cp=0;
}
else
{
D=Help_Sub(BB);
D.cp=1;
}
}
else
{
if(BB.m+1>LL_MAX)
a.resize(BB.m+1);
cp=BB.cp;m=BB.m;
for(i=0;i<=BB.m;i++)
a=BB.a;
BB=AA;
if(cp==BB.cp)
{
D=Help_Add(BB);
D.cp=cp;
}
else if((cp==0)&&(BB.cp==1))
{
D=Help_Sub(BB);
D.cp=0;
}
else
{
D=Help_Sub(BB);
D.cp=1;
}
}
if(AA.m+1>LL_MAX)a.resize(AA.m+1);
cp=AA.cp;
m=AA.m;
for(i=0;i<=AA.m;i++)
a=AA.a;
return D;
}
LLong LLong::operator-(const LLong &B)
{
LLong D,AA,BB=B;
if(m+1>LL_MAX)AA.a.resize(m+1);
for(int i=0;i<=m;i++)
AA.a=a;
AA.m=m;
AA.cp=cp;
if((LL_BJ(BB)==1)||(LL_BJ(BB)==0))
{
if(cp==BB.cp)
{
D=Help_Sub(BB);
D.cp=cp;
}
else if((cp==0)&&(BB.cp==1))
{
D=Help_Add(BB);
D.cp=0;
}
else
{
D=Help_Add(BB);
D.cp=1;
}
}
else
{
if(BB.m+1>LL_MAX)
a.resize(BB.m+1);
cp=BB.cp;m=BB.m;
for(i=0;i<=BB.m;i++)
a=BB.a;
BB=AA;
if(cp==BB.cp)
{
D=Help_Sub(BB);
if(cp==1)
D.cp=0;
if(cp==0)
D.cp=1;
}
else if((cp==0)&&(BB.cp==1))
{
D=Help_Add(BB);
D.cp=1;
}
else
{
D=Help_Add(BB);
D.cp=0;
}
}
if(AA.m+1>LL_MAX)a.resize(AA.m+1);
cp=AA.cp;
m=AA.m;
for(i=0;i<=m;i++)
a=AA.a;
return D;
}
LLong LLong::operator*(const LLong &B)
{
LLong F,D;
int i,j,k;
if(cp==B.cp)
k=0;
else
k=1;
LLong G=B;
G.cp=0;
for(j=0;j<=G.m;j++)
{
for(i=0;i<j+m+2;i++)/*sugaigua*/
{
if(i+1>LL_MAX)
D.a.resize(i+1);
D.a=0;
}
D.m=j+m+1;
for(i=j;i<=j+m;i++)
{
D.a=(D.a+G.a*a)/10000;
D.a=(D.a+G.a*a)%10000;
}
if(D.a==0)
D.m=j+m;
D.cp=0;
F=F+D;
}
F.cp=k;
return F;
}
LLong LLong::operator^(const LLong &B)
{
LLong AA,d,W,BB=B,T(1),D(1);
if(BB<W)
{
cout<<"指数不能负"<<endl;
return 1;
}
if(m+1>LL_MAX)AA.a.resize(m+1);
AA.m=m;
AA.cp=cp;
for(int i=0;i<=m;i++)
AA.a=a;
for(d=W;d<BB;d=d+T)
{
D=D*AA;
}
return D;
}
void LLong::LL_Div01(const LLong &B,LLong &Q,LLong &R)
{
int i,n;
LLong F,W,T(1);
LLong AA,BB=B;
if(m+1>LL_MAX)AA.a.resize(m+1);
AA.m=m;
AA.cp=cp;
for(i=0;i<=m;i++)
AA.a=a;
AA.cp=BB.cp=0;
if(LL_BJ(BB)==-1)
{
R=AA;
Q=W;
}
else if(LL_BJ(BB)==0)
{
R=W;
Q=T;
}
else
{
n=AA.m-BB.m;
for(i=0;i<n;i++)
{
if(i+1>LL_MAX)
F.a.resize(i+1);
F.a=0;
}
if(AA.a>=BB.a)
{
if(n+1>LL_MAX)F.a.resize(n+1);
F.a=AA.a/BB.a;
F.m=n;
}
else
{
F.a=(AA.a*10000+AA.a)/BB.a;
F.m=n-1;
}
F.cp=0;
Q=F;
R=AA-BB*F;
}
}
void LLong::LL_Div02(const LLong &B,LLong &Q,LLong &R)
{
LLong W,AA,BB=B;
if(m+1>LL_MAX)AA.a.resize(m+1);
AA.m=m;
AA.cp=cp;
for(int i=0;i<=m;i++)
AA.a=a;
BB.cp=0;
if(cp==0)
LL_Div01(BB,Q,R);
else
{
LL_Div01(BB,Q,R);
if(Q!=W)
Q.cp=1;
if(R!=W)
{
if(R.cp==0)
R.cp=1;
else
R.cp=0;
}
}
if(AA.m+1>LL_MAX)a.resize(AA.m+1);
cp=AA.cp;
m=AA.m;
for(i=0;i<=AA.m;i++)
a=AA.a;
return;
}
void LLong::LL_Div03(const LLong &B,LLong &Q,LLong &R)
{
LLong W,AAA,AA,QQ,RR,T(1),BB=B;
if(m+1>LL_MAX)AA.a.resize(m+1);
AA.m=m;
AA.cp=cp;
for(int i=0;i<=m;i++)
AA.a=a;
AAA=AA;
AA.cp=BB.cp=0;
while(1)
{
LL_Div02(BB,QQ,RR);
if(RR.m+1>LL_MAX)a.resize(RR.m+1);
cp=RR.cp;
m=RR.m;
for(i=0;i<=RR.m;i++)
a=RR.a;
if(LL_BJ(BB)==-1)
{
if(RR.cp==0)
{
R=RR;
Q=Q+QQ;
}
else
{
R=BB+RR;
Q=Q+QQ-T;
}
if(AAA.m+1>LL_MAX)a.resize(AAA.m+1);
cp=AAA.cp;
m=AAA.m;
for(i=0;i<=AAA.m;i++)
a=AAA.a;
return;
}
if(RR.m+1>LL_MAX)a.resize(RR.m+1);
cp=RR.cp;
m=RR.m;
for(i=0;i<=RR.m;i++)
a=RR.a;
Q=Q+QQ;
}
}
void LLong::LL_Div(const LLong &B,LLong &Q,LLong &R)
{
LLong W,AA,BB=B,AAA;
if(m+1>LL_MAX)AA.a.resize(m+1);
AA.m=m;
AA.cp=cp;
for(int i=0;i<=m;i++)
AA.a=a;
AAA=AA;
if(BB==W)
printf("Not to Div.");
if((AA.cp==0)&&(BB.cp==0))
LL_Div03(BB,Q,R);
else if((AA.cp==1)&&(BB.cp==1))
{
cp=0;BB.cp=0;
LL_Div03(BB,Q,R);
}
else if((AA.cp==1)&&(BB.cp==0))
{
cp=0;
LL_Div03(BB,Q,R);
if(Q!=W)
Q.cp=1;
if(R!=W)
R.cp=1;
}
else
{
LL_Div03(BB,Q,R);
if(Q!=W)
Q.cp=1;
}
if(AAA.m+1>LL_MAX)a.resize(AAA.m+1);
cp=AAA.cp;
m=AAA.m;
for(i=0;i<=AAA.m;i++)
a=AAA.a;
return;
}
LLong LLong::operator%(const LLong &B)
{
LLong Q,R;
LL_Div(B,Q,R);
return R;
}
LLong LLong::operator/(const LLong &B)
{
LLong Q,R;
LL_Div(B,Q,R);
return Q;
}
[ 本帖最后由 风花雪月 于 2006-11-29 07:30 编辑 ]
页:
[1]