3 条题解
-
2
c++的代码，真的好长
// luogu-judger-enable-o2 #include <bits/stdc++.h> class BigInt { #define Value(x, nega) ((nega) ? -(x) : (x)) #define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0) //C风格的比较函数,其正负等于abs(lhs)-abs(rhs)的正负 static int absComp(const BigInt &lhs, const BigInt &rhs) { if (lhs.size() != rhs.size()) return lhs.size() < rhs.size() ? -1 : 1; for (int i = lhs.size() - 1; i >= 0; --i) if (lhs[i] != rhs[i]) return lhs[i] < rhs[i] ? -1 : 1; return 0; } using Long = long long; const static int Exp = 9; const static Long Mod = 1000000000; mutable std::vector<Long> val; mutable bool nega = false; //规定:0的nega必须是false,0的size必须是0 void trim() const { while (val.size() && val.back() == 0) val.pop_back(); if (val.empty()) nega = false; } int size() const { return val.size(); } Long &operator[](int index) const { return val[index]; } Long &back() const { return val.back(); } BigInt(int size, bool nega) : val(size), nega(nega) {} BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {} public: friend std::ostream &operator<<(std::ostream &os, const BigInt &n) { if (n.size()) { if (n.nega) putchar('-'); for (int i = n.size() - 1; i >= 0; --i) { if (i == n.size() - 1) printf("%lld", n[i]); else printf("%0*lld", n.Exp, n[i]); } } else putchar('0'); return os; } friend BigInt operator+(const BigInt &lhs, const BigInt &rhs) { BigInt ret(lhs); return ret += rhs; } friend BigInt operator-(const BigInt &lhs, const BigInt &rhs) { BigInt ret(lhs); return ret -= rhs; } BigInt(Long x = 0) { if (x < 0) x = -x, nega = true; while (x >= Mod) val.push_back(x % Mod), x /= Mod; if (x) val.push_back(x); } BigInt(const char *s) { int bound = 0, pos; if (s[0] == '-') nega = true, bound = 1; Long cur = 0, pow = 1; for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1) for (int i = pos; i > pos - Exp; --i) cur += (s[i] - '0') * pow, pow *= 10; for (cur = 0, pow = 1; pos >= bound; --pos) cur += (s[pos] - '0') * pow, pow *= 10; if (cur) val.push_back(cur); } BigInt &operator+=(const BigInt &rhs) { const int cap = std::max(size(), rhs.size()) + 1; val.resize(cap); int carry = 0; for (int i = 0; i < cap - 1; ++i) { val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0; if (val[i] >= Mod) val[i] -= Mod, carry = 1; //至多只需要减一次，不需要取模 else if (val[i] < 0) val[i] += Mod, carry = -1; //同理 } if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1) { nega = true, val.pop_back(); bool tailZero = true; for (int i = 0; i < cap - 1; ++i) { if (tailZero && val[i]) val[i] = Mod - val[i], tailZero = false; else val[i] = Mod - 1 - val[i]; } } trim(); return *this; } friend BigInt operator-(const BigInt &rhs) { BigInt ret(rhs); ret.nega ^= 1; return ret; } BigInt &operator-=(const BigInt &rhs) { rhs.nega ^= 1; *this += rhs; rhs.nega ^= 1; return *this; } //高精*高精没办法原地操作，所以实现operator* //高精*低精可以原地操作，所以operator*= friend BigInt operator*(const BigInt &lhs, const BigInt &rhs) { const int cap = lhs.size() + rhs.size() + 1; BigInt ret(cap, lhs.nega ^ rhs.nega); //j < l.size(),i - j < rhs.size() => i - rhs.size() + 1 <= j for (int i = 0; i < cap - 1; ++i) // assert(0 <= ret[cap-1] < Mod) for (int j = std::max(i - rhs.size() + 1, 0), up = std::min(i + 1, lhs.size()); j < up; ++j) { ret[i] += lhs[j] * rhs[i - j]; ret[i + 1] += ret[i] / Mod, ret[i] %= Mod; } ret.trim(); return ret; } BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; } friend BigInt operator/(const BigInt &lhs, const BigInt &rhs) { static std::vector<BigInt> powTwo{BigInt(1)}; static std::vector<BigInt> estimate; estimate.clear(); if (absComp(lhs, rhs) < 0) return BigInt(); BigInt cur = rhs; int cmp; while ((cmp = absComp(cur, lhs)) <= 0) { estimate.push_back(cur), cur += cur; if (estimate.size() >= powTwo.size()) powTwo.push_back(powTwo.back() + powTwo.back()); } if (cmp == 0) return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega); BigInt ret = powTwo[estimate.size() - 1]; cur = estimate[estimate.size() - 1]; for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i) if ((cmp = absComp(cur + estimate[i], lhs)) <= 0) cur += estimate[i], ret += powTwo[i]; ret.nega = lhs.nega ^ rhs.nega; return ret; } bool operator==(const BigInt &rhs) const { return nega == rhs.nega && val == rhs.val; } bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; } bool operator>=(const BigInt &rhs) const { return !(*this < rhs); } bool operator>(const BigInt &rhs) const { return !(*this <= rhs); } bool operator<=(const BigInt &rhs) const { if (nega && !rhs.nega) return true; if (!nega && rhs.nega) return false; int cmp = absComp(*this, rhs); return nega ? cmp >= 0 : cmp <= 0; } bool operator<(const BigInt &rhs) const { if (nega && !rhs.nega) return true; if (!nega && rhs.nega) return false; return (absComp(*this, rhs) < 0) ^ nega; } void swap(const BigInt &rhs) const { std::swap(val, rhs.val); std::swap(nega, rhs.nega); } }; const int N = 1e4 + 10; char a[N], b[N]; int main() { scanf("%s%s", a, b); BigInt ba(a), bb(b); std::cout << ba + bb << '\n'; std::cout << ba - bb << '\n'; std::cout << ba * bb << '\n'; BigInt d; std::cout << (d = ba / bb) << '\n'; std::cout << ba - d * bb << '\n'; return 0; } -
0
#include <iostream> #include <string> #include <algorithm> using namespace std; // 比较两个大整数的大小（a是否大于等于b） bool isGreaterOrEqual(const string &a, const string &b) { if (a.length() != b.length()) return a.length() > b.length(); return a >= b; } // 大整数加法 string add(string a, string b) { string result; int carry = 0; int i = a.length() - 1, j = b.length() - 1; while (i >= 0 || j >= 0 || carry) { int digitA = (i >= 0) ? a[i--] - '0' : 0; int digitB = (j >= 0) ? b[j--] - '0' : 0; int sum = digitA + digitB + carry; result.push_back(sum % 10 + '0'); carry = sum / 10; } reverse(result.begin(), result.end()); return result; } // 大整数减法（a >= b） string subtract(string a, string b) { string result; int borrow = 0; int i = a.length() - 1, j = b.length() - 1; while (i >= 0) { int digitA = a[i--] - '0' - borrow; int digitB = (j >= 0) ? b[j--] - '0' : 0; if (digitA < digitB) { digitA += 10; borrow = 1; } else { borrow = 0; } result.push_back(digitA - digitB + '0'); } // 去除前导零 while (result.size() > 1 && result.back() == '0') result.pop_back(); reverse(result.begin(), result.end()); return result; } // 大整数乘法 string multiply(string a, string b) { if (a == "0" || b == "0") return "0"; vector<int> product(a.size() + b.size(), 0); for (int i = a.size() - 1; i >= 0; i--) { for (int j = b.size() - 1; j >= 0; j--) { int mul = (a[i] - '0') * (b[j] - '0'); int sum = mul + product[i + j + 1]; product[i + j + 1] = sum % 10; product[i + j] += sum / 10; } } string result; for (int digit : product) { if (!(result.empty() && digit == 0)) result.push_back(digit + '0'); } return result; } // 大整数除法（返回商和余数） pair<string, string> divide(string a, string b) { if (b == "0") return {"0", "0"}; // 除数为0处理 string quotient, remainder; for (char digit : a) { remainder.push_back(digit); int count = 0; while (isGreaterOrEqual(remainder, b)) { remainder = subtract(remainder, b); count++; } quotient.push_back(count + '0'); } // 去除前导零 quotient.erase(0, min(quotient.find_first_not_of('0'), quotient.size() - 1)); remainder.erase(0, min(remainder.find_first_not_of('0'), remainder.size() - 1)); if (quotient.empty()) quotient = "0"; if (remainder.empty()) remainder = "0"; return {quotient, remainder}; } int main() { string A, B; cin >> A >> B; // 和 cout << add(A, B) << endl; // 差 if (isGreaterOrEqual(A, B)) { cout << subtract(A, B) << endl; } else { cout << "-" << subtract(B, A) << endl; } // 积 cout << multiply(A, B) << endl; // 商和余数 auto [quotient, remainder] = divide(A, B); cout << quotient << endl; cout << remainder << endl; return 0; }
xxc2012
LV 10
@ 2025-4-1 19:25:28
- 1
