Big_Integer/Addition_of_Big_Integers.test.cpp

• View this file on GitHub
• Last update: 2025-05-25 00:26:18+07:00
• Problem: https://judge.yosupo.jp/problem/addition_of_big_integers

Depends on

• Big_Integer/BigInt.h
• template.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/addition_of_big_integers"

#include "../template.h"
#include "BigInt.h"

void solve(){
    int t; cin >> t;
    while (t--) {
        string s1, s2; cin >> s1 >> s2;
        BigInt a(s1), b(s2);
        cout << a + b << '\n';
    }
}

#line 1 "Big_Integer/Addition_of_Big_Integers.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/addition_of_big_integers"

#line 2 "template.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define INF32 ((1ull<<31)-1)
#define INF64 ((1ull<<63)-1)
#define inf (ll)1e18

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int mod = 998244353;

void solve();

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);
    // int t; cin >> t;
    // while(t--)
        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 2 "Big_Integer/BigInt.h"

class BigInt {
public:
    static const int BASE = 10;
    vector<uint32_t> digit;
    bool neg = false;

    BigInt() {}

    BigInt(int64_t val) {*this = val;}

    BigInt(const string &s) {*this = s;}

    uint32_t getDigit(const uint32_t i) const {return digit[i];}

    uint32_t size() const {return digit.size();}

    bool isZero() const {return digit.empty();}

    int compare(const BigInt &b) const {
        if (size() != b.size())
            return size() > b.size() ? 1 : -1;
        else if (size() < b.size())
            return -1;
        for (int i = (int)size()-1; i >= 0; i--) {
            if (digit[i] != b.getDigit(i))
                return digit[i] > b.getDigit(i) ? 1 : -1;
        }
        return 0;
    }

    void trim() {
        while (!digit.empty() && digit.back() == 0)
            digit.pop_back();
        if (digit.empty()) neg = false;
    }

    BigInt &operator=(int64_t val) {
        digit.clear();
        if (val < 0) {
            neg = true;
            val = -val;
        }
        while (val) {
            digit.push_back(val % BASE);
            val /= BASE;
        }
        return *this;
    }

    BigInt &operator=(const string &s) {
        digit.clear();
        int32_t pos = 0;
        if (s[0] == '-') {
            neg = true;
            pos = 1;
        }
        for (int i = (int)s.size()-1; i >= pos; i--) {
            digit.push_back(s[i]-'0');
        }
        trim();
        return *this;
    }

    friend ostream &operator<<(ostream &out, const BigInt &b) {
        if (b.isZero()) return out << "0";
        if (b.neg) out << "-";
        for (int i = (int)b.size()-1; i >= 0; i--)
            out << b.getDigit(i);
        return out;
    }

    BigInt operator+(const BigInt &b) const {
        BigInt res;
        if (neg == b.neg) {
            res.neg = neg;
            int carry = 0;
            size_t len = max(size(), b.size());
            for (size_t i = 0; i < len; i++) {
                int sum = carry;
                if (i < size()) sum += digit[i];
                if (i < b.size()) sum += b.getDigit(i);
                res.digit.push_back(sum % BASE);
                carry = sum / BASE;
            }
            if (carry) res.digit.push_back(carry);
            res.trim();
            return res;
        } else {
            return *this - (-b);
        }
    }

    BigInt operator-(const BigInt &b) const {
        if (!neg && b.neg)
            return *this + (-b);
        if (neg && !b.neg)
            return -((-*this) + b);
        if (compare(b) == -1) 
            return -(b - *this);
        BigInt res;
        res.neg = neg;
        int borrow = 0;
        for (size_t i = 0; i < digit.size(); i++) {
            int sub = digit[i]-borrow;
            if (i < b.size()) sub -= b.getDigit(i);
            if (sub < 0) sub += BASE, borrow = 1;
            else borrow = 0;
            res.digit.push_back(sub);
        }
        res.trim();
        return res;
    }

    BigInt operator-() const {
        BigInt res = *this;
        if (!res.isZero())
            res.neg = !neg;
        return res;
    }

    BigInt mul(const BigInt &a, const BigInt &b) const {
        BigInt x = a, y = b;
        x.trim(); y.trim();
        BigInt res;
        if (x.neg != y.neg)
            res.neg = true;
        res.digit.resize(x.size()+y.size());
        for (size_t i = 0; i < x.size(); i++) {
            int carry = 0;
            for (size_t j = 0; j < y.size(); j++) {
                int64_t cur = res.getDigit(i+j) + carry;
                cur += x.digit[i] * y.getDigit(j);
                res.digit[i+j] = cur % BASE;
                carry = cur / BASE;
            }
            if (carry) res.digit[i+y.size()] += carry;
        }
        res.trim();
        if (res.isZero()) res.neg = false;
        return res;
    }

    //---------------------karatsuba----------------------
    BigInt shifted(size_t k) const {
        if (isZero()) return *this;
        BigInt r = *this;
        r.digit.insert(r.digit.begin(), k, 0);
        return r;
    }    

    BigInt karatsuba(const BigInt &a, const BigInt &b) const {
        if (a.size() < 32 || b.size() < 32)
            return mul(a, b);
        size_t n = max(a.size(), b.size());
        uint32_t k = n / 2;

        BigInt a_low, a_high;
        a_low.digit.assign(a.digit.begin(), a.digit.begin() + min(k, a.size()));
        a_high.digit.assign(a.digit.begin() + min(k, a.size()), a.digit.end());
        a_low.neg = a_high.neg = false;
        a_low.trim();
        a_high.trim();

        BigInt b_low, b_high;
        b_low.digit.assign(b.digit.begin(), b.digit.begin() + min(k, b.size()));
        b_high.digit.assign(b.digit.begin() + min(k, b.size()), b.digit.end());
        b_low.neg = b_high.neg = false;
        b_low.trim();
        b_high.trim();

        BigInt z0 = karatsuba(a_low, b_low);
        BigInt z2 = karatsuba(a_high, b_high);
        BigInt z1 = karatsuba(a_low + a_high, b_low + b_high) - z0 - z2;

        BigInt res = z2.shifted(2*k) + z1.shifted(k) + z0;
        res.neg = (a.neg != b.neg);
        res.trim();
        return res;
    }

    BigInt operator*(const BigInt &b) const {
        return karatsuba(*this, b);
    }
};
#line 5 "Big_Integer/Addition_of_Big_Integers.test.cpp"

void solve(){
    int t; cin >> t;
    while (t--) {
        string s1, s2; cin >> s1 >> s2;
        BigInt a(s1), b(s2);
        cout << a + b << '\n';
    }
}

Back to top page