0x01紫书风格
#include <algorithm> // max #include <cassert> // assert #include <cstdio> // printf,sprintf #include <cstring> // strlen #include <iostream> // cin,cout #include <string> // string类 #include <vector> // vector类 using namespace std; struct biginteger { typedef unsigned long long ll; static const int base = 100000000; static const int width = 8; vector<int> s; biginteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;} biginteger(ll num = 0) {*this = num;} biginteger(string s) {*this = s;} biginteger& operator = (long long num) { s.clear(); do { s.push_back(num % base); num /= base; } while (num > 0); return *this; } biginteger& operator = (const string& str) { s.clear(); int x, len = (str.length() - 1) / width + 1; for (int i = 0; i < len; i++) { int end = str.length() - i*width; int start = max(0, end - width); sscanf(str.substr(start,end-start).c_str(), "%d", &x); s.push_back(x); } return (*this).clean(); } biginteger operator + (const biginteger& b) const { biginteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = g; if (i < s.size()) x += s[i]; if (i < b.s.size()) x += b.s[i]; c.s.push_back(x % base); g = x / base; } return c; } biginteger operator - (const biginteger& b) const { assert(b <= *this); // 减数不能大于被减数 biginteger c; c.s.clear(); for (int i = 0, g = 0; ; i++) { if (g == 0 && i >= s.size() && i >= b.s.size()) break; int x = s[i] + g; if (i < b.s.size()) x -= b.s[i]; if (x < 0) {g = -1; x += base;} else g = 0; c.s.push_back(x); } return c.clean(); } biginteger operator * (const biginteger& b) const { int i, j; ll g; vector<ll> v(s.size()+b.s.size(), 0); biginteger c; c.s.clear(); for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=ll(s[i])*b.s[j]; for (i = 0, g = 0; ; i++) { if (g ==0 && i >= v.size()) break; ll x = v[i] + g; c.s.push_back(x % base); g = x / base; } return c.clean(); } biginteger operator / (const biginteger& b) const { assert(b > 0); // 除数必须大于0 biginteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大 biginteger m; // 余数:初始化为0 for (int i = s.size()-1; i >= 0; i--) { m = m*base + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return c.clean(); } biginteger operator % (const biginteger& b) const { //方法与除法相同 biginteger c = *this; biginteger m; for (int i = s.size()-1; i >= 0; i--) { m = m*base + s[i]; c.s[i] = bsearch(b, m); m -= b*c.s[i]; } return m; } // 二分法找出满足bx<=m的最大的x int bsearch(const biginteger& b, const biginteger& m) const{ int l = 0, r = base-1, x; while (1) { x = (l+r)>>1; if (b*x<=m) {if (b*(x+1)>m) return x; else l = x;} else r = x; } } biginteger& operator += (const biginteger& b) {*this = *this + b; return *this;} biginteger& operator -= (const biginteger& b) {*this = *this - b; return *this;} biginteger& operator *= (const biginteger& b) {*this = *this * b; return *this;} biginteger& operator /= (const biginteger& b) {*this = *this / b; return *this;} biginteger& operator %= (const biginteger& b) {*this = *this % b; return *this;} bool operator < (const biginteger& b) const { if (s.size() != b.s.size()) return s.size() < b.s.size(); for (int i = s.size()-1; i >= 0; i--) if (s[i] != b.s[i]) return s[i] < b.s[i]; return false; } bool operator >(const biginteger& b) const{return b < *this;} bool operator<=(const biginteger& b) const{return !(b < *this);} bool operator>=(const biginteger& b) const{return !(*this < b);} bool operator!=(const biginteger& b) const{return b < *this || *this < b;} bool operator==(const biginteger& b) const{return !(b < *this) && !(b > *this);} }; ostream& operator << (ostream& out, const biginteger& x) { out << x.s.back(); for (int i = x.s.size()-2; i >= 0; i--) { char buf[20]; sprintf(buf, "%08d", x.s[i]); for (int j = 0; j < strlen(buf); j++) out << buf[j]; } return out; } istream& operator >> (istream& in, biginteger& x) { string s; if (!(in >> s)) return in; x = s; return in; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607740.html