2 条题解
-
45-何承哲 (938936) LV 9 MOD @ 2020-03-10 22:47:13
此处摘录较好同学答案
@陈朝
几乎所有同学没有重定义比较运算符?
//陈朝 201930390029 // 头文件 HugeInt.h #ifndef HUGEINT_H #define HUGEINT_H #include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; class HugeInt { private: int digit[100]; int len; public: HugeInt(); friend HugeInt operator+(const HugeInt&,const HugeInt&); friend HugeInt operator-(const HugeInt&,const HugeInt&); friend HugeInt operator*(const HugeInt&,const HugeInt&); friend istream &operator>>(istream&,HugeInt&); friend ostream &operator<<(ostream&,const HugeInt&); }; #endif //实现文件 HugeInt.cpp /* #include<bits/stdc++.h> #include"HugeInt.h" */ HugeInt::HugeInt() { for(int i=0;i<100;++i)digit[i]=0; len=0; } istream &operator>>(istream&input,HugeInt&a) { char s[100]; input>>s; a.len=strlen(s); for(int i=a.len-1;i>=0;--i) a.digit[i]=s[a.len-i-1]-'0'; //digit低位为数量级小 return input; } ostream &operator<<(ostream&op,const HugeInt&a) { for(int i=a.len-1;i>=0;--i) op<<a.digit[i]; return op; } HugeInt operator+(const HugeInt&a,const HugeInt&b) { HugeInt c; for(int i=0;i<a.len;++i) { c.digit[i]+=(a.digit[i]+b.digit[i]); if(c.digit[i]>=10) c.digit[i]%=10,c.digit[i+1]++; } if(c.digit[a.len]>0) c.len=a.len+1; else c.len=a.len; return c; } HugeInt operator-(const HugeInt&a,const HugeInt&b) { HugeInt c; int l1=0; for(int i=0;i<a.len;++i) { c.digit[i]+=(a.digit[i]-b.digit[i]); if(c.digit[i]<0) c.digit[i]=10+c.digit[i],c.digit[i+1]--; } for(int i=a.len-1;i>=0;--i) { if(c.digit[i]==0) l1++; else break; } c.len=a.len-l1; return c; } HugeInt operator*(const HugeInt&a,const HugeInt&b) { int l1=a.len; HugeInt c; for(int i=0;i<a.len;++i) { for(int j=0;j<b.len;++j) { c.digit[i+j]+=(a.digit[i]*b.digit[j]); if(c.digit[i+j]>=10) c.digit[i+j+1]+=c.digit[i+j]/10, c.digit[i+j]%=10; } } if(c.digit[a.len+b.len-1]) c.len=a.len+b.len; else c.len=a.len+b.len-1; return c; } //主程序 main.cpp /* #include<bits/stdc++.h> #include"HugeInt.h" */ int main() { HugeInt a,b; cin>>a; cin>>b; cout<<a+b<<endl <<a-b<<endl <<a*b; return 0; }
-
02020-03-10 22:53:52@
我的高精度模版
想了解的同学可以拿回去研究
使用vector进行储存以灵活利用空间和避免溢出
//万进制高精度模版 //负数支持 #include<iostream> #include<algorithm> #include<vector> #include<cmath> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<sstream> using namespace std; const int mod = 10000; const int digs = 4; typedef int typ;//低精类型 class bignum { private: vector<int> v;//储存值 int len;//长度 int flag;//1表示负数 public: bignum(); bignum(typ); bignum(const char*); bignum(string); bignum operator +(bignum); bignum operator -(bignum); bignum operator -(); bignum operator *(bignum); bignum operator /(typ); bignum operator %(typ); //比较运算实现>和== bool operator >(bignum); bool operator >=(bignum); bool operator <(bignum); bool operator <=(bignum); bool operator ==(bignum); bool operator !=(bignum); bignum& operator=(bignum); bignum& operator +=(bignum); bignum& operator -=(bignum); bignum& operator *=(bignum); bignum& operator /=(typ); bignum& operator %=(typ); bignum getdiv(typ, typ&); void print(); void clean();//去除前导0 string ToString(); const char* str(); friend istream& operator>>(istream&, bignum&); friend ostream& operator<<(ostream&, bignum); }; bignum::bignum() { v.clear(); len = 0; flag = 0; } bignum::bignum(typ val) :bignum() { if (val == 0) { v.push_back(0); len = 1; } if (val < 0) { flag = 1; val = -val; } while (val) { v.push_back(val % mod); val /= mod; } len = v.size(); } bignum::bignum(const char* s) :bignum() { if (s[0] == '-') flag = 1; else flag = 0; v.clear(); int p = 0; int i, j; int le = strlen(s); for (i = flag; i < le; i++) { p = p * 10 + s[i] - '0'; if ((le - i - 1) % digs == 0) { v.push_back(p); p = 0; } } len = v.size(); i = 0; j = len - 1; while (i < j) { swap(v[i], v[j]); i++; j--; } } bignum::bignum(string str) :bignum(str.c_str()) { //empty body } bignum bignum::operator+(bignum x) { if (flag ^ x.flag) { x.flag ^= 1; return *this - x; } bignum res; int l = min(len, x.len); int xx = 0; for (int i = 0; i < l; i++) { xx+=x.v[i] + v[i]; res.v.push_back(xx % mod); xx /= mod; } bignum& p = len > x.len ? *this : x; for (int i = l; i < p.len; i++) { xx += p.v[i]; res.v.push_back(xx % mod); xx /= mod; } if (xx) res.v.push_back(xx); res.len = res.v.size(); res.flag = flag; return res; } bignum bignum::operator-(bignum x) { if (flag ^ x.flag) { x.flag ^= 1; return *this + x; } bignum res = *this; int i; for (i = 0; i < x.len; i++) { if (i < len) res.v[i] -= x.v[i]; else res.v.push_back(-x.v[i]); } res.len = res.v.size(); if (res.v[res.len - 1] < 0) { res.flag ^= 1; for (i = 0; i < res.len;i++) { res.v[i] = -res.v[i]; } } for (i = res.len - 1; i > 0; i--) { if (res.v[i - 1] < 0) { res.v[i]--; res.v[i - 1] += mod; } } res.clean(); return res; } bignum bignum::operator-() { bignum res = *this; res.flag ^= 1; return res; } bignum bignum::operator*(bignum x) { int i, j, xx = 0; bignum res; res.len = len + x.len; for (i = 0; i < res.len; i++) res.v.push_back(0); for (i = 0; i < len; i++) for (j = 0; j < x.len; j++) { res.v[i + j] += v[i] * x.v[j]; if (res.v[i + j] > mod) { res.v[i + j + 1] += res.v[i + j] / mod; res.v[i + j] %= mod; } } for (i = 0; i < res.len - 1; i++) { res.v[i + 1] += res.v[i] / mod; res.v[i] %= mod; } res.clean(); res.flag = flag ^ x.flag; return res; } bignum bignum::operator/(typ x) { typ md; return this->getdiv(x, md); } bignum bignum::operator%(typ x) { typ res; getdiv(x, res); return bignum(res); } bool bignum::operator>(bignum x) { if (flag ^ x.flag) return flag ^ 1; if (len > x.len) return flag ^ 1; if (len < x.len) return flag; int i; for (i = len - 1; i >= 0; i--) { if (v[i] != x.v[i]) return flag ^ (v[i] > x.v[i]); } return false; } bool bignum::operator==(bignum x) { if (flag ^ x.flag) return false; if (len != x.len) return false; int i; for (i = 0; i < len; i++) if (v[i] != x.v[i]) return false; return true; } bool bignum::operator>=(bignum x) { return *this > x || *this == x; } bool bignum::operator<(bignum x) { return x > *this; } bool bignum::operator<=(bignum x) { return x >= * this; } bool bignum::operator!=(bignum x) { return !(*this == x); } bignum& bignum::operator=(bignum x) { len = x.len; flag = x.flag; v = x.v; return *this; } bignum& bignum::operator+=(bignum x) { *this = *this + x; return *this; } bignum& bignum::operator-=(bignum x) { *this = *this - x; return *this; } bignum& bignum::operator*=(bignum x) { *this = *this * x; return *this; } bignum& bignum::operator/=(typ x) { *this = *this / x; return *this; } bignum& bignum::operator%=(typ x) { *this = *this % x; return *this; } bignum bignum::getdiv(typ x, typ& mod_dest) { int p = 0,i; int fl = 0; bignum res; for (i = len - 1; i >= 0; i--) { p = p * mod + v[i]; if (p > x) { if (!fl) { res.len = i + 1; for (int j = 0; j < res.len; j++) res.v.push_back(0); fl = 1; } res.v[i] = p / x; p %= x; } } res.flag = (x < 0 ? 1 : 0) ^ flag; mod_dest = p; return res; } void bignum::print() { int i; if (flag) cout<<'-'; cout << v[len - 1]; for (i = len - 2; i >= 0; i--) cout << setfill('0') << setw(digs) << v[i]; } void bignum::clean() { while (v[len - 1] == 0) len--, v.pop_back(); } string bignum::ToString() { string res; stringstream ss; if(flag) res.push_back('-'); for (int i = len - 1; i >= 0; i--) { ss.str(""); ss << setw(digs) << setfill('0') << v[i]; res += ss.str(); } return res; } const char* bignum::str() { string s = ToString(); return s.c_str(); } istream& operator>>(istream& c, bignum& x) { string s; c >> s; x = bignum(s); return c; } ostream& operator<<(ostream& c, bignum x) { x.print(); return c; } int main() { bignum a, b; cin >> a >> b; cout << a + b << endl; cout << a - b << endl; cout << a * b << endl; }
- 1