高精度模板

#ifndef _CLASS_BIGINTEGER_ #define _CLASS_BIGINTEGER_ #include<string> #include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; typedef long long qword; struct Int128 { static const qword maxval=100000000000000000LLU; qword first,second; Int128(qword x,qword y):first(x),second(y){}; Int128(){}; inline void operator += (Int128& pp) { first+=pp.first; second+=pp.second; if (second>=maxval) { first++; second-=maxval; } } inline void operator -=(Int128& pp) { first-=pp.first; second-=pp.second; if (second<0) { second+=maxval; first--; } } }; class BigInteger { public: static const int maxlen=10; static const int maxval=10000; private: int numb[maxlen]; int len; bool sign; void Add(BigInteger &num); void Substract(BigInteger &num); void Multiply(const BigInteger &num); void Divide(const BigInteger &num); int AbsCompare(const BigInteger &num); int Compare(const BigInteger &num); public: BigInteger(); BigInteger(long long x); BigInteger(string str); string ToString()const; void operator =(const BigInteger &num); void operator +=(const BigInteger num); void operator -=(const BigInteger num); void operator *=(const BigInteger num); void operator /=(const BigInteger num); bool operator <(const BigInteger &num); bool operator <=(const BigInteger &num); bool operator >(const BigInteger &num); bool operator >=(const BigInteger &num); friend ostream& operator << (ostream& out,const BigInteger& num); friend istream& operator >> (istream& in,BigInteger& num); friend BigInteger operator +(BigInteger num1,BigInteger num2); friend BigInteger operator -(BigInteger num1,BigInteger num2); friend BigInteger operator *(BigInteger num1,BigInteger num2); }; #endif BigInteger::BigInteger() { memset(numb,0,sizeof(numb)); } BigInteger::BigInteger(long long x) { char s[20]; sprintf(s,"%lld",x); string str=s; *this=BigInteger(str); } BigInteger::BigInteger(string str) { memset(numb,0,sizeof(numb)); sign=false; if (str[0]=='-') { sign=true; str=str.substr(1,str.length()-1); } for (int i=0;i<(int)str.length();i++) { if (!isdigit(str[i]))throw "invalid number!"; numb[(str.length()-i-1)/4]=numb[(str.length()-i-1)/4]*10+str[i]-'0'; } len=(int)(str.length()-1)/4+1; while (len && !numb[len-1])len--; } void BigInteger::Add(BigInteger &num) { if (this->sign!=num.sign) { num.sign^=1; Substract(num); num.sign^=1; }else { len=max(len,num.len); for (int i=0;i<len;i++) numb[i]+=num.numb[i]; for (int i=0;i<len;i++) { numb[i+1]+=numb[i]/maxval; numb[i]%=maxval; } while (numb[len]) { numb[len+1]+=numb[len]/maxval; numb[len]%=maxval; if (len++==maxlen)throw "Out of range!"; } } } void BigInteger::Substract(BigInteger &num) { if (this->sign!=num.sign) { num.sign^=1; Add(num); num.sign^=1; }else { for (int i=0;i<len;i++) numb[i]-=num.numb[i]; for (int i=0;i<len;i++) { if (numb[i]<0) { numb[i]+=maxval; numb[i+1]--; } } if (numb[len]<0)throw "Substract Error!"; while (len && !numb[len-1])len--; } } int BigInteger::AbsCompare(const BigInteger &num) { if (this->len!=num.len) return this->len<num.len?-1:1; for (int i=this->len-1;i>=0;i--) { if (this->numb[i]!=num.numb[i]) return this->numb[i]<num.numb[i]?-1:1; } return 0; } int BigInteger::Compare(const BigInteger &num) { if (this->sign!=num.sign) return this->sign>num.len?-1:1; return AbsCompare(num); } string BigInteger::ToString()const { string res; if (len || numb[0]!=0)res=sign?"-":""; char cstr[5]; sprintf(cstr,"%d",numb[len-1]); res+=cstr; for (int i=len-2;i>=0;i--) { sprintf(cstr,"d",numb[i]); res+=cstr; } return res; } void BigInteger::operator =(const BigInteger &num) { memcpy(this,&num,sizeof(num)); } //void BigInteger::operator +=(BigInteger num){} //void BigInteger::operator -=(BigInteger num){} //void BigInteger::operator *=(BigInteger num){} //void BigInteger::operator /=(BigInteger num){} bool BigInteger::operator <(const BigInteger& num) { return this->Compare(num)<0; } bool BigInteger::operator <=(const BigInteger& num) { return this->Compare(num)<=0; } bool BigInteger::operator >(const BigInteger& num) { return this->Compare(num)>0; } bool BigInteger::operator >=(const BigInteger& num) { return this->Compare(num)>0; } ostream& operator << (ostream& out,const BigInteger& num) { string str; str=num.ToString(); out<<str; return out; } istream& operator >> (istream& in,BigInteger& num) { string str; in>>str; num=BigInteger(str); return in; } BigInteger operator + (BigInteger num1,BigInteger num2) { if (num1.AbsCompare(num2)>=0) { num1.Add(num2); return num1; }else { num2.Add(num1); return num2; } } BigInteger operator - (BigInteger num1,BigInteger num2) { if (num1.AbsCompare(num2)>=0) { num1.Substract(num2); return num1; }else { num2.Substract(num1); num2.sign^=1; return num2; } } BigInteger operator * (BigInteger num1,BigInteger num2) { BigInteger ret; ret.sign=num1.sign^num2.sign; ret.len=num1.len+num2.len; for (int i=0;i<num1.len;i++) for (int j=0;j<num2.len;j++) { ret.numb[i+j]+=num1.numb[i]*num2.numb[j]; ret.numb[i+j+1]+=ret.numb[i+j]/BigInteger::maxval; ret.numb[i+j]%=BigInteger::maxval; } for (int i=0;i<ret.len;i++) { ret.numb[i+1]+=ret.numb[i]/BigInteger::maxval; ret.numb[i]%=BigInteger::maxval; } while (ret.numb[ret.len]) { ret.numb[ret.len+1]=ret.numb[ret.len]/BigInteger::maxval; ret.numb[ret.len]%=BigInteger::maxval; ret.len++; } while (ret.len && !ret.numb[ret.len-1])ret.len--; return ret; } int main() { freopen("input.txt","r",stdin); BigInteger a,b,c;; cin>>a>>b; c=a*b; cout<<c<<endl; }

 

转载于:https://www.cnblogs.com/mhy12345/p/4307916.html