Advertisement
konchin_shih

Untitled

Aug 27th, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<vector>
  4. #include<algorithm>
  5. using namespace std;
  6. constexpr int carry = 1e9;
  7. istream& operator>>(istream& is, vector<long long>& v) {
  8.     string str; is >> str;
  9.     vector<long long>().swap(v);
  10.     while (str.size() >= 9)
  11.         v.emplace_back(atoi(str.substr(str.size() - 9).data())), str = str.substr(0, str.size() - 9);
  12.     v.emplace_back(atoi(str.data()));
  13.     return is;
  14. }
  15. bool operator<(const vector<long long>& a, const vector<long long>& b) {
  16.     if (a.size() != b.size()) return a.size() < b.size();
  17.     for (int i = a.size() - 1; i >= 0; i--)
  18.         if (a[i] != b[i]) return a[i] < b[i];
  19.     return false;
  20. }
  21. int main() {
  22.     char op;
  23.     string str1, str2;
  24.     vector<long long> a, b;
  25.     cin >> a >> op >> b;
  26.     auto minus = [](vector<long long>& a, const vector<long long>& b) {
  27.         long long tmp = 0;
  28.         for (size_t i = 0; i < b.size(); i++)
  29.             tmp += a[i] - b[i] + carry, a[i] = tmp % carry, tmp /= carry, tmp--;
  30.         for (size_t i = b.size(); i < a.size(); i++)
  31.             tmp += a[i] + carry, a[i] = tmp % carry, tmp /= carry, tmp--;
  32.         while (a.size() > 1 && !a.back()) a.pop_back();
  33.     };
  34.     auto multiply = [](vector<long long>& a, const vector<long long>& b) {
  35.         long long tmp = 0;
  36.         vector<long long> v(a.size() + b.size(), 0);
  37.         for (size_t i = 0; i < a.size(); i++) {
  38.             for (size_t j = 0; j < b.size(); j++)
  39.                 tmp += v[i + j] + a[i] * b[j], v[i + j] = tmp % carry, tmp /= carry;
  40.             for (size_t j = i; j < a.size(); j++)
  41.                 tmp += v[b.size() + j], v[b.size() + j] = tmp % carry, tmp /= carry;
  42.         } v.swap(a);
  43.         if (!a.back()) a.pop_back();
  44.     };
  45.     switch (op) {
  46.     case '+': {
  47.         long long tmp = 0;
  48.         a.resize(max(a.size(), b.size()), 0);
  49.         for (size_t i = 0; i < b.size(); i++)
  50.             tmp += a[i] + b[i], a[i] = tmp % carry, tmp /= carry;
  51.         for (size_t i = b.size(); i < a.size(); i++)
  52.             tmp += a[i], a[i] = tmp % carry, tmp /= carry;
  53.         if (tmp) a.emplace_back(tmp);
  54.     } break;
  55.     case '-': {
  56.         if (a < b) minus(b, a), a.swap(b), cout << '-'; else minus(a, b);
  57.     } break;
  58.     case '*': {
  59.         multiply(a, b);
  60.     } break;
  61.     case '/': {
  62.         if (a < b) {a.assign({0}); break;}
  63.         long long tmp = 0;
  64.         vector<long long> v(a.size() - b.size() + 1, 0), arr;
  65.         for (int i = a.size() - b.size(); i >= 0; i--) {
  66.             multiply(arr = b, {v[i] = (a[b.size() + i - 1] + tmp) / b.back()});
  67.             arr.resize(arr.size() + i);
  68.             move_backward(arr.begin(), arr.begin() + arr.size() - i, arr.end());
  69.             minus(a, arr);
  70.             if (a.size() < arr.size()) tmp = 0;
  71.             else tmp = a.back() * carry, a.pop_back();
  72.         }
  73.         minus(v, {0}), a.swap(v);
  74.     } break;
  75.     }
  76.     cout << a.back();
  77.     for (int i = a.size() - 2; i >= 0; i--)
  78.         cout << setfill('0') << setw(9) << a[i]/* << ' '*/;
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement