高精度加减乘模板
这是我将紫书上的高精度模板和 Menci 的高精度模板进行一定程度的修改得到的自己的板子。
其中要注意的是高精度减法需要均为正数,且大数减小数。如何比较大小?模板里面重载了 < 运算符,可以直接比较大小。
修改结构体中的 WIDTH
与 BASE
可以达到修改压位的位数的目的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| struct BigInt { static const int BASE = 10000; static const int WIDTH = 4; int s[10005], n; BigInt(long long num = 0) {*this = num;} BigInt operator = (long long num) { memset(s, 0, sizeof(s)); n = 0; do{ s[++n] = num % BASE; num /= BASE; } while(num > 0); return *this; } BigInt operator = (const string& str) { memset(s, 0, sizeof(s)); n = 0; 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[++n] = x; } return *this; } BigInt operator + (const BigInt& b) const { BigInt c; memset(c.s, 0, sizeof(c.s)); c.n = 0; for(int i = 1, g = 0; ; i++) { if(g == 0 && i > n && i > b.n) break; int x = g; if(i <= n) x += s[i]; if(i <= b.n) x += b.s[i]; c.s[++c.n] = x % BASE; g = x / BASE; } return c; } BigInt operator * (const BigInt& b) const { BigInt c; memset(c.s, 0, sizeof(c.s)); c.n = n + b.n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= b.n; j++) { c.s[i + j - 1] += s[i] * b.s[j]; c.s[i + j] += c.s[i + j - 1] / BASE; c.s[i + j - 1] %= BASE; } } while(c.n > 1 && c.s[c.n] == 0) c.n--; return c; } BigInt operator - (const BigInt& b) const { BigInt c; memset(c.s, 0, sizeof(c.s)); c.n = 0; bool flag = false; for(int i = 1; i <= n; i++) { int x = s[i]; if(i <= b.n) x -= b.s[i]; if(flag) x--, flag = false; if(x < 0) x += BASE, flag = true; c.s[++c.n] = x; } while(c.n > 1 && c.s[c.n] == 0) c.n--; return c; } bool operator < (const BigInt& b) const { if(n != b.n) return n < b.n; for(int i = n; i >= 1; i--) if(s[i] != b.s[i]) return s[i] < b.s[i]; return false; } };
ostream& operator << (ostream& out, const BigInt& x) { out << x.s[x.n]; for(int i = x.n - 1; i >= 1; i--) { out << setw(4) << setfill('0') << x.s[i]; } return out; }
istream& operator >> (istream& in, BigInt& x) { string s; if(!(in >> s)) return in; x = s; return in; }
|