Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define getchar getchar_unlocked
- using namespace std;
- class Number {
- int sign;
- [[maybe_unused]] void add_lz(size_t count) {
- while (count--) {
- digits.push_back(0);
- }
- }
- void add_tz(size_t count) {
- while (count--) {
- digits.push_front(0);
- }
- clear_lz();
- }
- void clear_lz() {
- while (digits.size() > 1 && digits.back() == 0) {
- digits.pop_back();
- }
- }
- [[nodiscard]] Number native_multiply(const Number& one, const Number& other) const {
- size_t n = max(length(), other.length());
- Number result(one.sign * other.sign, 2 * n);
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (i < length() && j < other.length()) {
- result.digits[i + j] += (*this)[i] * other[j];
- }
- }
- }
- int transposition = 0;
- for (int i = 0; i < 2 * n; i++) {
- result.digits[i] += transposition % 10;
- transposition /= 10;
- if (result[i] > 9) {
- transposition += result[i] / 10;
- result.digits[i] %= 10;
- }
- }
- while (transposition) {
- result.digits.push_back(transposition % 10);
- transposition /= 10;
- }
- result.clear_lz();
- return result;
- }
- static pair<Number, Number> split(const Number& number, size_t middle) {
- Number first;
- for (size_t i = min(number.length(), middle); i < number.length(); ++i) {
- first.digits.push_back(number[i]);
- }
- first.clear_lz();
- Number second;
- for (size_t i = 0; i < min(number.length(), middle); ++i) {
- second.digits.push_back(number[i]);
- }
- second.clear_lz();
- return {first, second};
- }
- protected:
- deque<int> digits;
- Number(int sign, size_t size) : sign(sign), digits(size, 0) {}
- Number(int sign, const deque<int>& digits) : sign(sign), digits(digits) {
- if (sign != 1 && sign != -1) {
- throw invalid_argument("Wrong sign");
- }
- clear_lz();
- }
- int operator [] (size_t index) const {
- if (index >= length()) {
- throw out_of_range("Out of range");
- }
- return digits[index];
- }
- public:
- [[nodiscard]] const deque<int>& getDigits() const {
- return digits;
- }
- [[nodiscard]] size_t length() const {
- return digits.size();
- }
- Number() : sign(1), digits() {}
- explicit Number(string& s) {
- sign = 1;
- for (auto digit : s) {
- digits.push_front(digit - '0');
- }
- clear_lz();
- }
- bool operator < (const Number& other) {
- if (length() < other.length()) {
- return true;
- }
- if (length() > other.length()) {
- return false;
- }
- for (int i = length() - 1; i >= 0; --i) {
- if ((*this)[i] < other[i]) {
- return true;
- }
- if ((*this)[i] > other[i]) {
- return false;
- }
- }
- return false;
- }
- Number operator + (const Number& other) {
- if (sign != other.sign) {
- Number first = *this;
- Number second = other;
- if (first.sign == -1) {
- swap(first, second);
- }
- second.sign = 1;
- return first - second;
- }
- Number result(sign, max(length(), other.length()) + 1);
- bool transposition = false;
- for (int i = 0; i <= max(length(), other.length()); ++i) {
- result.digits[i] = transposition;
- if (i < length()) {
- result.digits[i] += (*this)[i];
- }
- if (i < other.length()) {
- result.digits[i] += other[i];
- }
- if (result[i] > 9) {
- transposition = true;
- result.digits[i] -= 10;
- } else {
- transposition = false;
- }
- }
- result.clear_lz();
- return result;
- }
- Number operator - (const Number& other) {
- if (sign != other.sign) {
- Number first = *this;
- Number second = other;
- if (first.sign == -1) {
- second.sign = -1;
- } else {
- second.sign = 1;
- }
- return first + second;
- }
- if (*this < other) {
- Number first = *this;
- Number second = other;
- return second - first;
- }
- Number result(sign, max(digits.size(), other.digits.size()));
- int transposition = 0;
- for (int i = 0; i < max(length(), other.length()); ++i) {
- result.digits[i] = transposition;
- if (i < length()) {
- result.digits[i] += (*this)[i];
- }
- if (i < other.length()) {
- result.digits[i] -= other[i];
- }
- if (result[i] < 0) {
- transposition = -1;
- result.digits[i] += 10;
- } else {
- transposition = 0;
- }
- }
- result.clear_lz();
- return result;
- }
- Number operator * (const Number& other) {
- size_t n = max(length(), other.length());
- if (n <= 64) {
- return native_multiply(*this, other);
- }
- size_t middle = n / 2;
- auto [A1, A2] = split(*this, static_cast<int>(middle));
- auto [B1, B2] = split(other, static_cast<int>(middle));
- Number C1 = A1 * B1;
- Number C2 = A2 * B2;
- Number C3 = (A1 + A2) * (B1 + B2) - C1 - C2;
- C3.add_tz(middle);
- C1.add_tz(2 * middle);
- Number result = C1 + C2 + C3;
- result.clear_lz();
- return result;
- }
- void readNumber() {
- int s = 1, c = getchar();
- while (c != '-' && !('0' <= c && c <= '9')) {
- c = getchar();
- }
- if (c == '-')
- sign = -1, c = getchar();
- else
- sign = 1;
- while ('0' <= c && c <= '9')
- digits.push_front(c - '0'), c = getchar();
- }
- };
- ostream& operator << (ostream& out, const Number& number) {
- for (auto it = number.getDigits().end(); it != number.getDigits().begin(); ) {
- --it;
- cout << *it;
- }
- return out;
- }
- int32_t main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- Number a, b;
- a.readNumber();
- b.readNumber();
- cout << a * b;
- }
Advertisement
Add Comment
Please, Sign In to add comment