ProgMe

SUKA KARATSUBA

Oct 21st, 2023
1,095
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.74 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define getchar getchar_unlocked
  4.  
  5. using namespace std;
  6.  
  7. class Number {
  8.     int sign;
  9.  
  10.     [[maybe_unused]] void add_lz(size_t count) {
  11.         while (count--) {
  12.             digits.push_back(0);
  13.         }
  14.     }
  15.  
  16.     void add_tz(size_t count) {
  17.         while (count--) {
  18.             digits.push_front(0);
  19.         }
  20.         clear_lz();
  21.     }
  22.  
  23.     void clear_lz() {
  24.         while (digits.size() > 1 && digits.back() == 0) {
  25.             digits.pop_back();
  26.         }
  27.     }
  28.  
  29.     [[nodiscard]] Number native_multiply(const Number& one, const Number& other) const {
  30.         size_t n = max(length(), other.length());
  31.         Number result(one.sign * other.sign, 2 * n);
  32.  
  33.         for (int i = 0; i < n; i++) {
  34.             for (int j = 0; j < n; j++) {
  35.                 if (i < length() && j < other.length()) {
  36.                     result.digits[i + j] += (*this)[i] * other[j];
  37.                 }
  38.             }
  39.         }
  40.  
  41.         int transposition = 0;
  42.         for (int i = 0; i < 2 * n; i++) {
  43.             result.digits[i] += transposition % 10;
  44.             transposition /= 10;
  45.  
  46.             if (result[i] > 9) {
  47.                 transposition += result[i] / 10;
  48.                 result.digits[i] %= 10;
  49.             }
  50.         }
  51.         while (transposition) {
  52.             result.digits.push_back(transposition % 10);
  53.             transposition /= 10;
  54.         }
  55.         result.clear_lz();
  56.  
  57.         return result;
  58.     }
  59.  
  60.     static pair<Number, Number> split(const Number& number, size_t middle) {
  61.         Number first;
  62.         for (size_t i = min(number.length(), middle); i < number.length(); ++i) {
  63.             first.digits.push_back(number[i]);
  64.         }
  65.         first.clear_lz();
  66.  
  67.         Number second;
  68.         for (size_t i = 0; i < min(number.length(), middle); ++i) {
  69.             second.digits.push_back(number[i]);
  70.         }
  71.         second.clear_lz();
  72.  
  73.         return {first, second};
  74.     }
  75.  
  76. protected:
  77.     deque<int> digits;
  78.  
  79.     Number(int sign, size_t size) : sign(sign), digits(size, 0) {}
  80.  
  81.     Number(int sign, const deque<int>& digits) : sign(sign), digits(digits) {
  82.         if (sign != 1 && sign != -1) {
  83.             throw invalid_argument("Wrong sign");
  84.         }
  85.         clear_lz();
  86.     }
  87.  
  88.     int operator [] (size_t index) const {
  89.         if (index >= length()) {
  90.             throw out_of_range("Out of range");
  91.         }
  92.         return digits[index];
  93.     }
  94.  
  95. public:
  96.     [[nodiscard]] const deque<int>& getDigits() const {
  97.         return digits;
  98.     }
  99.  
  100.     [[nodiscard]] size_t length() const {
  101.         return digits.size();
  102.     }
  103.  
  104.     Number() : sign(1), digits() {}
  105.  
  106.     explicit Number(string& s) {
  107.         sign = 1;
  108.         for (auto digit : s) {
  109.             digits.push_front(digit - '0');
  110.         }
  111.         clear_lz();
  112.     }
  113.  
  114.     bool operator < (const Number& other) {
  115.         if (length() < other.length()) {
  116.             return true;
  117.         }
  118.         if (length() > other.length()) {
  119.             return false;
  120.         }
  121.         for (int i = length() - 1; i >= 0; --i) {
  122.             if ((*this)[i] < other[i]) {
  123.                 return true;
  124.             }
  125.             if ((*this)[i] > other[i]) {
  126.                 return false;
  127.             }
  128.         }
  129.         return false;
  130.     }
  131.  
  132.     Number operator + (const Number& other) {
  133.         if (sign != other.sign) {
  134.             Number first = *this;
  135.             Number second = other;
  136.  
  137.             if (first.sign == -1) {
  138.                 swap(first, second);
  139.             }
  140.             second.sign = 1;
  141.  
  142.             return first - second;
  143.         }
  144.         Number result(sign, max(length(), other.length()) + 1);
  145.  
  146.         bool transposition = false;
  147.         for (int i = 0; i <= max(length(), other.length()); ++i) {
  148.             result.digits[i] = transposition;
  149.  
  150.             if (i < length()) {
  151.                 result.digits[i] += (*this)[i];
  152.             }
  153.             if (i < other.length()) {
  154.                 result.digits[i] += other[i];
  155.             }
  156.  
  157.             if (result[i] > 9) {
  158.                 transposition = true;
  159.                 result.digits[i] -= 10;
  160.             } else {
  161.                 transposition = false;
  162.             }
  163.         }
  164.         result.clear_lz();
  165.  
  166.         return result;
  167.     }
  168.  
  169.     Number operator - (const Number& other) {
  170.         if (sign != other.sign) {
  171.             Number first = *this;
  172.             Number second = other;
  173.  
  174.             if (first.sign == -1) {
  175.                 second.sign = -1;
  176.             } else {
  177.                 second.sign = 1;
  178.             }
  179.  
  180.             return first + second;
  181.         }
  182.         if (*this < other) {
  183.             Number first = *this;
  184.             Number second = other;
  185.             return second - first;
  186.         }
  187.  
  188.         Number result(sign, max(digits.size(), other.digits.size()));
  189.  
  190.         int transposition = 0;
  191.         for (int i = 0; i < max(length(), other.length()); ++i) {
  192.             result.digits[i] = transposition;
  193.  
  194.             if (i < length()) {
  195.                 result.digits[i] += (*this)[i];
  196.             }
  197.             if (i < other.length()) {
  198.                 result.digits[i] -= other[i];
  199.             }
  200.  
  201.             if (result[i] < 0) {
  202.                 transposition = -1;
  203.                 result.digits[i] += 10;
  204.             } else {
  205.                 transposition = 0;
  206.             }
  207.         }
  208.         result.clear_lz();
  209.  
  210.         return result;
  211.     }
  212.  
  213.     Number operator * (const Number& other) {
  214.         size_t n = max(length(), other.length());
  215.         if (n <= 64) {
  216.             return native_multiply(*this, other);
  217.         }
  218.  
  219.         size_t middle = n / 2;
  220.         auto [A1, A2] = split(*this, static_cast<int>(middle));
  221.         auto [B1, B2] = split(other, static_cast<int>(middle));
  222.  
  223.         Number C1 = A1 * B1;
  224.         Number C2 = A2 * B2;
  225.         Number C3 = (A1 + A2) * (B1 + B2) - C1 - C2;
  226.  
  227.         C3.add_tz(middle);
  228.         C1.add_tz(2 * middle);
  229.  
  230.         Number result = C1 + C2 + C3;
  231.         result.clear_lz();
  232.  
  233.         return result;
  234.     }
  235.  
  236.     void readNumber() {
  237.         int s = 1, c = getchar();
  238.         while (c != '-' && !('0' <= c && c <= '9')) {
  239.             c = getchar();
  240.         }
  241.  
  242.         if (c == '-')
  243.             sign = -1, c = getchar();
  244.         else
  245.             sign = 1;
  246.  
  247.         while ('0' <= c && c <= '9')
  248.             digits.push_front(c - '0'), c = getchar();
  249.     }
  250. };
  251.  
  252. ostream& operator << (ostream& out, const Number& number) {
  253.     for (auto it = number.getDigits().end(); it != number.getDigits().begin(); ) {
  254.         --it;
  255.         cout << *it;
  256.     }
  257.     return out;
  258. }
  259.  
  260. int32_t main() {
  261.     ios::sync_with_stdio(false);
  262.     cin.tie(nullptr);
  263.     Number a, b;
  264.     a.readNumber();
  265.     b.readNumber();
  266.     cout << a * b;
  267. }
  268.  
Advertisement
Add Comment
Please, Sign In to add comment