12tqian's Competitive Programming Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub 12tqian/cp-library

:heavy_check_mark: verify/unit-test/unit-test-big-integer.test.cpp

Depends on

Code

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

#include "../../library/contest/template-full.hpp"
#include "../../library/numerical/big-integer.hpp"

void test() {
	const int D = 1000;
	const int T = 100;
	auto convert = [&](BigInt x) {
		mi res = 0;
		mi run = 1;
		f0r(i, sz(x.z)) {
			res += x.z[i] * run;
			run *= base;
		}
		if (x.sign == -1) {
			res *= -1;
		}
		return res;
	};
	f0r(t, T) {
		BigInt a = random_big_int(D) * ((rng() % 2) * 2 - 1) ;
		BigInt b = random_big_int(D) * ((rng() % 2) * 2 - 1);
		mi c = convert(a);
		mi d = convert(b);
		assert(convert(a + b) == c + d);
		assert(convert(a * b) == c * d);
		assert(convert(a - b) == c - d);
	}
}

int main() {
	set_io("");
	test();
	int a, b;
	re(a, b);
	ps(a + b);
	return 0;
}
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"



#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<db, db> pd;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define resz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define f1r(i, a, b) for (int i = (a); i < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define r1f(i, a, b) for (int i = (b); i --> (a); )
#define r0f(i, a) r1f(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define each(a, x) for (auto& a : x)

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<V<V<T>>>;
template <class T> using VVVV = V<V<V<V<T>>>>;

template <typename T, typename S> ostream& operator<<(ostream& os, const pair<T, S>& p) { 
  return os << "(" << p.first << ", " << p.second << ")"; 
}
template <typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream& os, const C& c) { 
  bool f = true; 
  os << "{"; 
  for (const auto& x : c) { 
    if (!f) 
      os << ", "; 
    f = false; os << x; 
  } 
  return os << "}"; 
}
template <typename T> void debug(string s, T x) { cerr << s << " = " << x << "\n"; }
template <typename T, typename... Args> void debug(string s, T x, Args... args) { 
  cerr << s.substr(0, s.find(',')) << " = " << x << " | "; 
  debug(s.substr(s.find(',') + 2), args...); 
}

constexpr int pct(int x) { return __builtin_popcount(x); }
constexpr int bits(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))


inline namespace Helpers {
	//////////// is_iterable

	// https://stackoverflow.com/questions/13830158/check-if-a-variable-type-is-iterable

	// this gets used only when we can call begin() and end() on that type

	template <class T, class = void> struct is_iterable : false_type {};
	template <class T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),
									  decltype(end(declval<T>()))
									 >
						   > : true_type {};
	template <class T> constexpr bool is_iterable_v = is_iterable<T>::value;

	//////////// is_readable

	template <class T, class = void> struct is_readable : false_type {};
	template <class T> struct is_readable<T,
			typename std::enable_if_t<
				is_same_v<decltype(cin >> declval<T&>()), istream&>
			>
		> : true_type {};
	template <class T> constexpr bool is_readable_v = is_readable<T>::value;

	//////////// is_printable

	// // https://nafe.es/posts/2020-02-29-is-printable/

	template <class T, class = void> struct is_printable : false_type {};
	template <class T> struct is_printable<T,
			typename std::enable_if_t<
				is_same_v<decltype(cout << declval<T>()), ostream&>
			>
		> : true_type {};
	template <class T> constexpr bool is_printable_v = is_printable<T>::value;
}

inline namespace Input {
	template <class T> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>;
	template <class T, class... U> void re(T& t, U&... u);
	template <class T, class U> void re(pair<T, U>& p); // pairs


	// re: read

	template <class T> typename enable_if<is_readable_v<T>, void>::type re(T& x) { cin >> x; } // default

	template <class T> void re(complex<T>& c) { T a, b; re(a, b); c = {a, b}; } // complex

	template <class T> typename enable_if<needs_input_v<T>, void>::type re(T& i); // ex. vectors, arrays

	template <class T, class U> void re(pair<T, U>& p) { re(p.first, p.second); }
	template <class T> typename enable_if<needs_input_v<T>, void>::type re(T& i) {
		for (auto& x : i) re(x); }
	template <class T, class... U> void re(T& t, U&... u) { re(t); re(u...); } // read multiple


	// rv: resize and read vectors

	void rv(std::size_t) {}
	template <class T, class... U> void rv(std::size_t N, vector<T>& t, U&... u);
	template <class...U> void rv(std::size_t, std::size_t N2, U&... u);
	template <class T, class... U> void rv(std::size_t N, vector<T>& t, U&... u) {
		t.resize(N); re(t);
		rv(N, u...); }
	template <class...U> void rv(std::size_t, std::size_t N2, U&... u) {
		rv(N2, u...); }

	// dumb shortcuts to read in ints

	void decrement() {} // subtract one from each

	template <class T, class... U> void decrement(T& t, U&... u) { --t; decrement(u...); }
	#define ints(...) int __VA_ARGS__; re(__VA_ARGS__);
	#define int1(...) ints(__VA_ARGS__); decrement(__VA_ARGS__);
}
  
inline namespace ToString {
	template <class T> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>;

	// ts: string representation to print

	template <class T> typename enable_if<is_printable_v<T>, string>::type ts(T v) {
		stringstream ss; ss << fixed << setprecision(15) << v;
		return ss.str(); } // default

	template <class T> string bit_vec(T t) { // bit vector to string

		string res = "{"; for (int i = 0; i < (int)t.size(); ++i) res += ts(t[i]);
		res += "}"; return res; }
	string ts(vector<bool> v) { return bit_vec(v); }
	template <std::size_t SZ> string ts(bitset<SZ> b) { return bit_vec(b); } // bit vector

	template <class T, class U> string ts(pair<T, U> p); // pairs

	template <class T> typename enable_if<needs_output_v<T>, string>::type ts(T v); // vectors, arrays

	template <class T, class U> string ts(pair<T, U> p) { return "(" + ts(p.first) + ", " + ts(p.second) + ")"; }
	template <class T> typename enable_if<is_iterable_v<T>, string>::type ts_sep(T v, string sep) { 
		// convert container to string w/ separator sep

		bool fst = 1; string res = "";
		for (const auto& x : v) { 
			if (!fst) res += sep;
			fst = 0; res += ts(x);
		}
		return res;
	}
	template <class T> typename enable_if<needs_output_v<T>, string>::type ts(T v) {
		return "{" + ts_sep(v, ", ") + "}"; } 

	// for nested DS

	template <int, class T> typename enable_if<!needs_output_v<T>, vector<string>>::type 
	  ts_lev(const T& v) { return {ts(v)}; }
	template <int lev, class T> typename enable_if<needs_output_v<T>, vector<string>>::type 
	  ts_lev(const T& v) {
		if (lev == 0 || !(int)v.size()) return {ts(v)};
		vector<string> res;
		for (const auto& t : v) {
			if ((int)res.size()) res.back() += ",";
			vector<string> tmp = ts_lev<lev - 1>(t);
			res.insert(res.end(), tmp.begin(), tmp.end()); 
		}
		for (int i = 0; i < (int)res.size(); ++i) {
			string bef = " "; if (i == 0) bef = "{";
			res[i] = bef + res[i];
		}
		res.back() += "}";
		return res;
	}
}

inline namespace Output {
	template <class T> void pr_sep(ostream& os, string, const T& t) { os << ts(t); }
	template <class T, class... U> void pr_sep(ostream& os, string sep, const T& t, const U&... u) {
		pr_sep(os, sep, t); os << sep; pr_sep(os, sep, u...); }
	// print w/ no spaces

	template <class... T> void pr(const T&... t) { pr_sep(cout, "", t...); } 
	// print w/ spaces, end with newline

	void ps() { cout << "\n"; }
	template <class... T> void ps(const T&... t) { pr_sep(cout, " ", t...); ps(); } 
	// debug to cerr

	template <class... T> void dbg_out(const T&... t) {
		pr_sep(cerr, " | ", t...); cerr << endl; }
	void loc_info(int line, string names) {
		cerr << "Line(" << line << ") -> [" << names << "]: "; }
	template <int lev, class T> void dbgl_out(const T& t) {
		cerr << "\n\n" << ts_sep(ts_lev<lev>(t), "\n") << "\n" << endl; }
	#ifdef LOCAL
		#define dbg(...) loc_info(__LINE__, #__VA_ARGS__), dbg_out(__VA_ARGS__)
		#define dbgl(lev, x) loc_info(__LINE__, #x), dbgl_out<lev>(x)
	#else // don't actually submit with this
		#define dbg(...) 0
		#define dbgl(lev, x) 0
	#endif
}

inline namespace FileIO {
	void set_in(string s)  { (void)!freopen(s.c_str(), "r", stdin); }
	void set_out(string s) { (void)!freopen(s.c_str(), "w", stdout); }
	void set_io(string s = "") {
		cin.tie(0)->sync_with_stdio(0); // unsync C / C++ I/O streams

		// cin.exceptions(cin.failbit);

		// throws exception when do smth illegal

		// ex. try to read letter into int

		if (!s.empty()) set_in(s + ".in"), set_out(s + ".out"); // for old USACO

	}
}

const int MOD = 1e9 + 7; // 998244353


typedef std::decay<decltype(MOD)>::type mod_t; 
struct mi {
	mod_t v;
	explicit operator mod_t() const { return v; }
	explicit operator bool() const { return v != 0; }
	mi() { v = 0; }
	mi(const long long& _v) {
		v = (-MOD <= _v && _v < MOD) ? _v : _v % MOD;
		if (v < 0) v += MOD; }
	friend std::istream& operator>>(std::istream& in, mi& a) { 
		long long x; std::cin >> x; a = mi(x); return in; }
	friend std::ostream& operator<<(std::ostream& os, const mi& a) { return os << a.v; }
	friend bool operator==(const mi& a, const mi& b) { return a.v == b.v; }
	friend bool operator!=(const mi& a, const mi& b) { return !(a == b); }    
	friend bool operator<(const mi& a, const mi& b) { return a.v < b.v; }
	friend bool operator>(const mi& a, const mi& b) { return a.v > b.v; }
	friend bool operator<=(const mi& a, const mi& b) { return a.v <= b.v; }
	friend bool operator>=(const mi& a, const mi& b) { return a.v >= b.v; }
	mi operator-() const { return mi(-v); }
	mi& operator+=(const mi& m) {
		if ((v += m.v) >= MOD) v -= MOD;
		return *this; }
	mi& operator-=(const mi& m) {
		if ((v -= m.v) < 0) v += MOD;
		return *this; }
	mi& operator*=(const mi& m) { v = (long long)v * m.v % MOD;
		return *this; }
	friend mi pow(mi a, long long p) {
		mi ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p & 1) ans *= a;
		return ans; }
	friend mi inv(const mi& a) { assert(a != 0); return pow(a, MOD - 2); }
	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
	friend mi operator+(mi a, const mi& b) { return a += b; }
	friend mi operator-(mi a, const mi& b) { return a -= b; }
	friend mi operator*(mi a, const mi& b) { return a *= b; }
	friend mi operator/(mi a, const mi& b) { return a /= b; }
};

const ld PI = acos((ld)-1);

typedef pair<mi, mi> pmi;
typedef vector<mi> vmi;
typedef vector<pmi> vpmi;

// base and base_digits must be consistent

constexpr int base = 1000000000;
constexpr int base_digits = 9;

struct BigInt {
	// value == 0 is represented by empty z

	std::vector<int> z; // digits


	// sign == 1 <==> value >= 0

	// sign == -1 <==> value < 0

	int sign;

	BigInt() : sign(1) {}
	BigInt(long long v) { *this = v; }

	BigInt& operator=(long long v) {
		sign = v < 0 ? -1 : 1; v *= sign;
		z.clear(); for (; v > 0; v = v / base) z.push_back((int) (v % base));
		return *this;
	}

	BigInt(const std::string& s) { read(s); }

	BigInt& operator+=(const BigInt& other) {
		if (sign == other.sign) {
			for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
				if (i == z.size())
					z.push_back(0);
				z[i] += carry + (i < other.z.size() ? other.z[i] : 0);
				carry = z[i] >= base;
				if (carry)
					z[i] -= base;
			}
		} else if (other != 0 /* prevent infinite loop */) {
			*this -= -other;
		}
		return *this;
	}

	friend BigInt operator+(BigInt a, const BigInt& b) { return a += b; }

	BigInt& operator-=(const BigInt& other) {
		if (sign == other.sign) {
			if (sign == 1 && *this >= other || sign == -1 && *this <= other) {
				for (int i = 0, carry = 0; i < other.z.size() || carry; ++i) {
					z[i] -= carry + (i < other.z.size() ? other.z[i] : 0);
					carry = z[i] < 0;
					if (carry)
						z[i] += base;
				}
				trim();
			} else {
				*this = other - *this;
				this->sign = -this->sign;
			}
		} else {
			*this += -other;
		}
		return *this;
	}

	friend BigInt operator-(BigInt a, const BigInt& b) { return a -= b; }

	BigInt& operator*=(int v) {
		if (v < 0) sign = -sign, v = -v;
		for (int i = 0, carry = 0; i < z.size() || carry; ++i) {
			if (i == z.size())
				z.push_back(0);
			long long cur = (long long) z[i] * v + carry;
			carry = (int) (cur / base);
			z[i] = (int) (cur % base);
		}
		trim();
		return *this;
	}

	BigInt operator*(int v) const { return BigInt(*this) *= v; }

	friend std::pair<BigInt, BigInt> divmod(const BigInt& a1, const BigInt& b1) {
		int norm = base / (b1.z.back() + 1);
		BigInt a = a1.abs() * norm;
		BigInt b = b1.abs() * norm;
		BigInt q, r;
		q.z.resize(a.z.size());

		for (int i = (int) a.z.size() - 1; i >= 0; i--) {
			r *= base;
			r += a.z[i];
			int s1 = b.z.size() < r.z.size() ? r.z[b.z.size()] : 0;
			int s2 = b.z.size() - 1 < r.z.size() ? r.z[b.z.size() - 1] : 0;
			int d = (int) (((long long) s1 * base + s2) / b.z.back());
			r -= b * d;
			while (r < 0)
				r += b, --d;
			q.z[i] = d;
		}

		q.sign = a1.sign * b1.sign;
		r.sign = a1.sign;
		q.trim();
		r.trim();
		return {q, r / norm};
	}

	friend BigInt sqrt(const BigInt& a1) {
		BigInt a = a1;
		while (a.z.empty() || a.z.size() % 2 == 1)
			a.z.push_back(0);

		int n = a.z.size();

		int firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
		int norm = base / (firstDigit + 1);
		a *= norm;
		a *= norm;
		while (a.z.empty() || a.z.size() % 2 == 1)
			a.z.push_back(0);

		BigInt r = (long long) a.z[n - 1] * base + a.z[n - 2];
		firstDigit = (int) ::sqrt((double) a.z[n - 1] * base + a.z[n - 2]);
		int q = firstDigit;
		BigInt res;

		for (int j = n / 2 - 1; j >= 0; j--) {
			for (;; --q) {
				BigInt r1 = (r - (res * 2 * base + q) * q) * base * base +
							(j > 0 ? (long long) a.z[2 * j - 1] * base + a.z[2 * j - 2] : 0);
				if (r1 >= 0) {
					r = r1;
					break;
				}
			}
			res *= base;
			res += q;

			if (j > 0) {
				int d1 = res.z.size() + 2 < r.z.size() ? r.z[res.z.size() + 2] : 0;
				int d2 = res.z.size() + 1 < r.z.size() ? r.z[res.z.size() + 1] : 0;
				int d3 = res.z.size() < r.z.size() ? r.z[res.z.size()] : 0;
				q = (int) (((long long) d1 * base * base + (long long) d2 * base + d3) / (firstDigit * 2));
			}
		}

		res.trim();
		return res / norm;
	}

	BigInt operator/(const BigInt& v) const { return divmod(*this, v).first; }

	BigInt operator%(const BigInt& v) const { return divmod(*this, v).second; }

	BigInt& operator/=(int v) {
		if (v < 0) sign = -sign, v = -v;
		for (int i = (int) z.size() - 1, rem = 0; i >= 0; --i) {
			long long cur = z[i] + rem * (long long) base;
			z[i] = (int) (cur / v);
			rem = (int) (cur % v);
		}
		trim();
		return *this;
	}

	BigInt operator/(int v) const { return BigInt(*this) /= v; }

	int operator%(int v) const {
		if (v < 0) v = -v;
		int m = 0;
		for (int i = (int) z.size() - 1; i >= 0; --i)
			m = (int) ((z[i] + m * (long long) base) % v);
		return m * sign;
	}

	BigInt& operator*=(const BigInt& v) { return *this = *this * v; }
	BigInt& operator/=(const BigInt& v) { return *this = *this / v; }

	bool operator<(const BigInt& v) const {
		if (sign != v.sign)
			return sign < v.sign;
		if (z.size() != v.z.size())
			return z.size() * sign < v.z.size() * v.sign;
		for (int i = (int) z.size() - 1; i >= 0; i--)
			if (z[i] != v.z[i])
				return z[i] * sign < v.z[i] * sign;
		return false;
	}

	bool operator>(const BigInt& v) const { return v < *this; }
	bool operator<=(const BigInt& v) const { return !(v < *this); }
	bool operator>=(const BigInt& v) const { return !(*this < v); }
	bool operator==(const BigInt& v) const { return !(*this < v) && !(v < *this); }
	bool operator!=(const BigInt& v) const { return *this < v || v < *this; }

	void trim() {
		while (!z.empty() && z.back() == 0) z.pop_back();
		if (z.empty()) sign = 1;
	}

	bool is_zero() const { return z.empty(); }

	friend BigInt operator-(BigInt v) {
		if (!v.z.empty()) v.sign = -v.sign;
		return v;
	}

	BigInt abs() const { return sign == 1 ? *this : -*this; }

	long long longValue() const {
		long long res = 0;
		for (int i = (int) z.size() - 1; i >= 0; i--)
			res = res * base + z[i];
		return res * sign;
	}

	friend BigInt gcd(const BigInt& a, const BigInt& b) {
		return b.is_zero() ? a : gcd(b, a % b);
	}

	friend BigInt lcm(const BigInt& a, const BigInt& b) {
		return a / gcd(a, b) * b;
	}

	void read(const std::string& s) {
		sign = 1;
		z.clear();
		int pos = 0;
		while (pos < s.size() && (s[pos] == '-' || s[pos] == '+')) {
			if (s[pos] == '-')
				sign = -sign;
			++pos;
		}
		for (int i = (int) s.size() - 1; i >= pos; i -= base_digits) {
			int x = 0;
			for (int j = std::max(pos, i - base_digits + 1); j <= i; j++)
				x = x * 10 + s[j] - '0';
			z.push_back(x);
		}
		trim();
	}

	friend std::istream& operator>>(std::istream& stream, BigInt& v) {
		std::string s; stream >> s;
		v.read(s);
		return stream;
	}

	friend std::ostream& operator<<(std::ostream& stream, const BigInt& v) {
		if (v.sign == -1)
			stream << '-';
		stream << (v.z.empty() ? 0 : v.z.back());
		for (int i = (int) v.z.size() - 2; i >= 0; --i)
			stream << std::setw(base_digits) << std::setfill('0') << v.z[i];
		return stream;
	}

	static std::vector<int> convert_base(const std::vector<int>& a, int old_digits, int new_digits) {
		std::vector<long long> p(std::max(old_digits, new_digits) + 1);
		p[0] = 1;
		for (int i = 1; i < p.size(); i++)
			p[i] = p[i - 1] * 10;
		std::vector<int> res;
		long long cur = 0;
		int cur_digits = 0;
		for (int v : a) {
			cur += v * p[cur_digits];
			cur_digits += old_digits;
			while (cur_digits >= new_digits) {
				res.push_back(int(cur % p[new_digits]));
				cur /= p[new_digits];
				cur_digits -= new_digits;
			}
		}
		res.push_back((int) cur);
		while (!res.empty() && res.back() == 0)
			res.pop_back();
		return res;
	}

	static std::vector<long long> karatsubaMultiply(const std::vector<long long>& a, const std::vector<long long>& b) {
		int n = a.size();
		std::vector<long long> res(n + n);
		if (n <= 32) {
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					res[i + j] += a[i] * b[j];
			return res;
		}

		int k = n >> 1;
		std::vector<long long> a1(a.begin(), a.begin() + k);
		std::vector<long long> a2(a.begin() + k, a.end());
		std::vector<long long> b1(b.begin(), b.begin() + k);
		std::vector<long long> b2(b.begin() + k, b.end());

		std::vector<long long> a1b1 = karatsubaMultiply(a1, b1);
		std::vector<long long> a2b2 = karatsubaMultiply(a2, b2);

		for (int i = 0; i < k; i++)
			a2[i] += a1[i];
		for (int i = 0; i < k; i++)
			b2[i] += b1[i];

		std::vector<long long> r = karatsubaMultiply(a2, b2);
		for (int i = 0; i < a1b1.size(); i++)
			r[i] -= a1b1[i];
		for (int i = 0; i < a2b2.size(); i++)
			r[i] -= a2b2[i];

		for (int i = 0; i < r.size(); i++)
			res[i + k] += r[i];
		for (int i = 0; i < a1b1.size(); i++)
			res[i] += a1b1[i];
		for (int i = 0; i < a2b2.size(); i++)
			res[i + n] += a2b2[i];
		return res;
	}

	BigInt operator*(const BigInt& v) const {
		std::vector<int> a6 = convert_base(this->z, base_digits, 6);
		std::vector<int> b6 = convert_base(v.z, base_digits, 6);
		std::vector<long long> a(a6.begin(), a6.end());
		std::vector<long long> b(b6.begin(), b6.end());
		while (a.size() < b.size())
			a.push_back(0);
		while (b.size() < a.size())
			b.push_back(0);
		while (a.size() & (a.size() - 1))
			a.push_back(0), b.push_back(0);
		std::vector<long long> c = karatsubaMultiply(a, b);
		BigInt res;
		res.sign = sign * v.sign;
		for (int i = 0, carry = 0; i < c.size(); i++) {
			long long cur = c[i] + carry;
			res.z.push_back((int) (cur % 1000000));
			carry = (int) (cur / 1000000);
		}
		res.z = convert_base(res.z, 6, base_digits);
		res.trim();
		return res;
	}
};

BigInt random_big_int(int n) {
	std::string s;
	for (int i = 0; i < n; i++) {
		s += rand() % 10 + '0';
	}
	return BigInt(s);
}

void test() {
	const int D = 1000;
	const int T = 100;
	auto convert = [&](BigInt x) {
		mi res = 0;
		mi run = 1;
		f0r(i, sz(x.z)) {
			res += x.z[i] * run;
			run *= base;
		}
		if (x.sign == -1) {
			res *= -1;
		}
		return res;
	};
	f0r(t, T) {
		BigInt a = random_big_int(D) * ((rng() % 2) * 2 - 1) ;
		BigInt b = random_big_int(D) * ((rng() % 2) * 2 - 1);
		mi c = convert(a);
		mi d = convert(b);
		assert(convert(a + b) == c + d);
		assert(convert(a * b) == c * d);
		assert(convert(a - b) == c - d);
	}
}

int main() {
	set_io("");
	test();
	int a, b;
	re(a, b);
	ps(a + b);
	return 0;
}
Back to top page