Library
This documentation is automatically generated by online-judge-tools/verification-helper
Big_Integer/Yosupo/Unit_test_math.test.cpp
- View this file on GitHub
- Last update: 2026-07-26 19:50:18+07:00
- Problem: https://judge.yosupo.jp/problem/aplusb
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "../../template.h"
#include "../BigInt_full.h"
using B = BigInt<>; // D = 9
using B4 = BigInt<4>; // cung logic, khac limb -> doi chieu cheo
using B1 = BigInt<1>;
string i128str(__int128 v) {
if (v == 0) return "0";
bool neg = v < 0; if (neg) v = -v;
string s;
while (v) { s += char('0' + int(v % 10)); v /= 10; }
if (neg) s += '-';
reverse(s.begin(), s.end());
return s;
}
// so sanh hai so nguyen dang chuoi, doc lap hoan toan voi BigInt
int refCmp(string x, string y) {
int sx = 1, sy = 1;
if (x[0] == '-') { sx = -1; x = x.substr(1); }
if (y[0] == '-') { sy = -1; y = y.substr(1); }
x.erase(0, min(x.find_first_not_of('0'), x.size() - 1));
y.erase(0, min(y.find_first_not_of('0'), y.size() - 1));
if (x == "0") sx = 0;
if (y == "0") sy = 0;
if (sx != sy) return sx < sy ? -1 : 1;
int c = x.size() != y.size() ? (x.size() < y.size() ? -1 : 1)
: (x == y ? 0 : (x < y ? -1 : 1));
return sx >= 0 ? c : -c;
}
string rndDigits(int n, mt19937 &g, bool neg = false) {
string s;
if (neg) s += '-';
s += char('1' + g() % 9);
for (int i = 1; i < n; i++) s += char('0' + g() % 10);
return s;
}
void solve() {
mt19937 g(20260726);
// ---------- 1. khoi tao va in ra ----------
assert(B().toString() == "0");
assert(B(0).toString() == "0");
assert(B("0").toString() == "0");
assert(B("-0").toString() == "0");
assert(B("0000123").toString() == "123");
assert(B("-0000123").toString() == "-123");
assert(B(LLONG_MAX).toString() == "9223372036854775807");
assert(B(LLONG_MIN + 1).toString() == "-9223372036854775807");
for (int t = 0; t < 300; t++) {
string s = rndDigits(1 + g() % 60, g, g() & 1);
assert(B(s).toString() == s);
assert(B4(s).toString() == s);
assert(B1(s).toString() == s);
}
// ---------- 2. so 0 chi co MOT bieu dien ----------
vector<B> zeros = {B(), B(0), B("0"), B("-0"), B(5) - B(5), B(0) * B(-7)};
{ B t(-10); t %= 5LL; zeros.push_back(t); }
{ B t(-10); t /= 3LL; t /= 4LL; zeros.push_back(t); }
for (const B &z : zeros) {
assert(z.isZero() && z.sign == 1 && z.toString() == "0");
for (const B &w : zeros)
assert(z == w && !(z < w) && !(z > w) && z <= w && z >= w);
}
// ---------- 3. so hoc doi chieu long long ----------
vector<ll> smalls;
for (ll x = -40; x <= 40; x++) smalls.push_back(x);
for (ll x : {999999998LL, 999999999LL, 1000000000LL, 1000000001LL,
-1000000000LL, 123456789012345LL, -987654321098765LL}) smalls.push_back(x);
for (ll a : smalls) for (ll b : smalls) {
B A(a), B_(b);
assert((A + B_) == B(a + b));
assert((A - B_) == B(a - b));
assert((A * B_).toString() == i128str((__int128)a * b));
assert((A < B_) == (a < b) && (A > B_) == (a > b) && (A == B_) == (a == b));
assert((A <= B_) == (a <= b) && (A >= B_) == (a >= b) && (A != B_) == (a != b));
assert((A < b) == (a < b) && (A == b) == (a == b) && (A >= b) == (a >= b));
if (b != 0) {
assert((A / B_) == B(a / b)); // chat ve 0, giong C++
assert((A % B_) == B(a % b));
assert(A / B_ * B_ + A % B_ == A); // bat bien
}
if (b != 0 && llabs(b) <= 1000000000LL) {
B q = A, r = A;
q /= b; r %= b;
assert(q == B(a / b) && r == B(a % b));
}
}
// ---------- 3b. so sanh ky: nhieu limb, co limb bang 0 ----------
{
vector<string> v = {"0", "-0", "1", "-1", "999999999", "-999999999",
"1000000000", "-1000000000", "1000000005", "-1000000005",
"1000000000000000000", "-1000000000000000000",
"1000000000000000001", "-1000000000000000001",
"2000000000", "-2000000000", "999999999999999999", "-999999999999999999",
"1000000000000000000000000000", "-1000000000000000000000000000",
"1000000000000000000000000001", "-1000000000000000000000000001"};
for (int t = 0; t < 200; t++) {
string s;
int limbs = 1 + g() % 4;
for (int i = 0; i < limbs; i++) {
int d = (g() % 3 == 0) ? 0 : (int)(g() % 1000000000);
string p = to_string(d);
s += string(9 - p.size(), '0') + p;
}
s.erase(0, min(s.find_first_not_of('0'), s.size() - 1));
v.push_back(s);
v.push_back("-" + s);
}
for (const string &x : v) for (const string &y : v) {
int c = refCmp(x, y);
B a(x), b(y);
assert((a < b) == (c < 0));
assert((a > b) == (c > 0));
assert((a == b) == (c == 0));
assert((a <= b) == (c <= 0));
assert((a >= b) == (c >= 0));
assert((a != b) == (c != 0));
}
}
// ---------- 4. don nguyen, tang giam ----------
for (ll x : {-7LL, -1LL, 0LL, 1LL, 9LL}) {
B a(x);
assert((-a) == B(-x) && (+a) == B(x) && (-(-a)) == a);
B b = a; assert((++b) == B(x + 1) && b == B(x + 1));
B c = a; assert((c++) == B(x) && c == B(x + 1));
B d = a; assert((--d) == B(x - 1));
B e = a; assert((e--) == B(x) && e == B(x - 1));
}
assert((-B(0)).sign == 1 && (-B(0)).toString() == "0");
// ---------- 5. int op BigInt (friend) ----------
assert((100LL + B(23)) == B(123));
assert((100LL - B(23)) == B(77));
assert((100LL * B(23)) == B(2300));
assert((100LL / B(23)) == B(4));
assert((100LL % B(23)) == B(8));
// ---------- 6. so lon: doi chieu cheo D=9 / D=4 / D=1 ----------
for (int t = 0; t < 40; t++) {
int la = 50 + g() % 700, lb = 50 + g() % 700; // vuot nguong karatsuba
string sa = rndDigits(la, g, g() & 1), sb = rndDigits(lb, g, false);
B a(sa), b(sb);
B4 a4(sa), b4(sb);
B1 a1(sa), b1(sb);
assert((a + b).toString() == (a4 + b4).toString());
assert((a - b).toString() == (a4 - b4).toString());
assert((a * b).toString() == (a4 * b4).toString());
assert((a / b).toString() == (a4 / b4).toString());
assert((a % b).toString() == (a4 % b4).toString());
assert((a * b).toString() == (a1 * b1).toString());
assert(a / b * b + a % b == a);
}
// ---------- 7. dong nhat thuc so lon ----------
for (int k : {1, 5, 20, 100, 400}) {
B p = pow(B(10), B(k));
assert(p.toString() == "1" + string(k, '0'));
assert((p - 1) * (p + 1) == pow(B(10), B(2 * k)) - 1);
B a = p - 1, b = p + 7;
assert((a + b) * (a + b) == a * a + 2 * (a * b) + b * b);
assert((a - b) * (a + b) == a * a - b * b);
}
B f1(1); for (int i = 1; i <= 100; i++) f1 *= i;
B f2(1); for (int i = 100; i >= 1; i--) f2 = f2 * i;
assert(f1 == f2);
assert(f1.toString().size() == 158); // 100! co 158 chu so
assert(f1 % 101 == B(100)); // wilson: 100! = -1 (mod 101)
// ---------- 8. sqrt ----------
for (ll x = 0; x <= 400; x++) {
assert(sqrt(B(x * x)) == B(x));
if (x) assert(sqrt(B(x * x + x)) == B(x));
if (x) assert(sqrt(B(x * x - 1)) == B(x - 1));
}
for (int t = 0; t < 30; t++) {
B a(rndDigits(1 + g() % 60, g)), r = sqrt(a);
assert(r * r <= a && (r + 1) * (r + 1) > a);
}
// ---------- 9. pow ----------
for (ll a = 2; a <= 12; a++) for (ll e = 0; e <= 15; e++) {
ll p = 1; for (ll i = 0; i < e; i++) p *= a;
assert(pow(B(a), B(e)) == B(p));
assert(pow(B(a), B(e), 1000000007LL) == B(p % 1000000007));
}
assert(pow(B(7), B(0)) == B(1));
assert(pow(B(0), B(5)) == B(0));
for (ll a : {2LL, 3LL, 123456LL}) // fermat
assert(pow(B(a), B(1000000006LL), 1000000007LL) == B(1));
// ---------- 10. gcd / lcm ----------
for (ll a = -30; a <= 30; a++) for (ll b = -30; b <= 30; b++) {
B G = __gcd(B(a), B(b));
assert(G == B(__gcd(llabs(a), llabs(b))) && G >= B(0));
B L = __lcm(B(a), B(b));
if (a == 0 || b == 0) assert(L == B(0));
else assert(L == B(llabs(a) / __gcd(llabs(a), llabs(b)) * llabs(b)));
}
{
B gg = pow(B(10), B(30)) + 7;
assert(__gcd(B(999983) * gg, B(1000003) * gg) == gg);
}
// ---------- 11. abs / isZero / size ----------
assert(B(-123).abs() == B(123) && B(0).abs().sign == 1);
assert(B(0).isZero() && !B(1).isZero());
assert(B(0).size() == 0 && B("999999999").size() == 1 && B("1000000000").size() == 2);
// ---------- 12. stream khong bi ban ----------
{ ostringstream os; os << B("1000000000000000000") << setw(5) << 42;
assert(os.str() == "1000000000000000000 42"); }
{ istringstream is("-123456789012345678901234567890"); B a; is >> a;
assert(a.toString() == "-123456789012345678901234567890"); }
ll a, b; cin >> a >> b;
cout << a + b << '\n';
}#line 1 "Big_Integer/Yosupo/Unit_test_math.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#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
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll r) { return uniform_int_distribution<ll>(0, r - 1)(rng); }
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_full.h"
// Still slow ver, need optimize by FFT
// This template only work for base <= 10
constexpr int pow10c(int k) { return k ? 10 * pow10c(k - 1) : 1; }
template<int D = 9>
class BigInt {
public:
static const int BASE_DIGITS = D;
static const int BASE = pow10c(D);
int sign;
vector<uint32_t> digit;
BigInt(): sign(1) {}
BigInt(const string &s) { *this = s; }
BigInt(int64_t val) { *this = val; }
BigInt &operator = (const string &s) {
read(s);
return *this;
}
BigInt &operator = (int64_t val) {
sign = val >= 0 ? 1 : -1;
val = llabs(val);
digit.clear();
for (; val; val /= BASE) {
digit.push_back(val % BASE);
}
trim();
return *this;
}
BigInt &operator += (const BigInt &b) {
if (sign != b.sign) {
BigInt t = b;
t.sign *= -1;
return *this -= t;
}
int carry = 0, len = (int)max(size(), b.size());
for (int i = 0; i < len; i++) {
int sum = carry;
if (i < (int)size()) sum += digit[i];
if (i < (int)b.size()) sum += b[i];
if (i < (int)size()) digit[i] = sum % BASE;
else digit.push_back(sum % BASE);
carry = sum / BASE;
}
if (carry) digit.push_back(carry);
trim();
return *this;
}
BigInt &operator -= (const BigInt &b) {
if (sign != b.sign) {
return *this += (-b);
}
if (__compare_abs(b) == -1) {
BigInt t = b;
t -= *this;
t.sign *= -1;
return *this = t;
}
int borrow = 0, len = (int)max(size(), b.size());
for (int i = 0; i < len; i++) {
int sub = -borrow;
if (i < (int)size()) sub += digit[i];
if (i < (int)b.size()) sub -= b[i];
if (sub < 0) sub += BASE, borrow = 1;
else borrow = 0;
digit[i] = sub;
}
trim();
return *this;
}
BigInt &operator *= (const BigInt &b) {
return *this = karatsuba(*this, b);
}
BigInt &operator /= (const BigInt &b) {
*this = divmod(*this, b).first;
return *this;
}
BigInt &operator %= (const BigInt &b) {
*this = divmod(*this, b).second;
return *this;
}
// ------------------------ Operator ------------------------
// BigInt += Int
BigInt &operator += (int64_t t) { return *this += BigInt(t); }
BigInt &operator -= (int64_t t) { return *this -= BigInt(t); }
BigInt &operator *= (int64_t t) { return *this *= BigInt(t); }
BigInt &operator /= (int64_t t) {
assert(t != 0); // not divided for 0
if (t < 0) {
sign = -sign;
t = -t;
}
int64_t rem = 0;
for (int i = (int)size() - 1; i >= 0; i--) {
int64_t cur = rem * BASE + (*this)[i];
(*this)[i] = uint32_t(cur / t);
rem = cur % t;
}
trim();
return *this;
}
BigInt &operator %= (int64_t t) {
assert(t != 0);
int64_t rem = 0;
for (int i = (int)size() - 1; i >= 0; i--) {
int64_t cur = rem * BASE + (*this)[i];
rem = cur % t;
}
if (rem < 0) rem += llabs(t);
int s = sign;
*this = rem;
if (!isZero()) sign = s;
return *this;
}
BigInt operator - () const { BigInt res = *this; res *= -1; return res; } // -a;
BigInt operator + () const { return BigInt(*this); } // +a;
BigInt &operator ++ () { *this += 1; return *this; } // ++a;
BigInt &operator -- () { *this -= 1; return *this; } // --a;
BigInt operator ++ (int) { BigInt res = *this; *this += 1; return res; } // a++;
BigInt operator -- (int) { BigInt res = *this; *this -= 1; return res; } // a--;
// BigInt = BigInt + BigInt
BigInt operator + (const BigInt &b) const { return BigInt(*this) += b; }
BigInt operator - (const BigInt &b) const { return BigInt(*this) -= b; }
BigInt operator * (const BigInt &b) const { return BigInt(*this) *= b; }
BigInt operator / (const BigInt &b) const { return BigInt(*this) /= b; }
BigInt operator % (const BigInt &b) const { return BigInt(*this) %= b; }
// BigInt = BigInt + Int
BigInt operator + (int64_t t) const { return BigInt(*this) += t; }
BigInt operator - (int64_t t) const { return BigInt(*this) -= t; }
BigInt operator * (int64_t t) const { return BigInt(*this) *= t; }
BigInt operator / (int64_t t) const { return BigInt(*this) /= t; }
BigInt operator % (int64_t t) const { return BigInt(*this) %= t; }
// BigInt = Int + BigInt
friend BigInt operator + (int64_t t, const BigInt &b) { BigInt res(t); res += b; return res; }
friend BigInt operator - (int64_t t, const BigInt &b) { BigInt res(t); res -= b; return res; }
friend BigInt operator * (int64_t t, const BigInt &b) { BigInt res(t); res *= b; return res; }
friend BigInt operator / (int64_t t, const BigInt &b) { BigInt res(t); res /= b; return res; }
friend BigInt operator % (int64_t t, const BigInt &b) { BigInt res(t); res %= b; return res; }
uint32_t operator [] (const int i) const { assert(i >= 0 && i < (int)size()); return digit[i]; }
uint32_t &operator [] (const int i) { assert(i >= 0 && i < (int)size()); return digit[i]; }
// ------------------------- Comparison ---------------------
bool operator < (const BigInt &b) const {
if (sign != b.sign) {
return sign < b.sign;
}
int c = __compare_abs(b);
return sign == 1 ? c < 0 : c > 0;
}
bool operator > (const BigInt &b) const { return b < *this; }
bool operator <= (const BigInt &b) const { return !(b < *this); }
bool operator >= (const BigInt &b) const { return !(*this < b); }
bool operator == (const BigInt &b) const { return !(*this < b) && !(b < *this); }
bool operator != (const BigInt &b) const { return *this < b || b < *this; }
bool operator == (int64_t t) const { return *this == BigInt(t); }
bool operator != (int64_t t) const { return *this != BigInt(t); }
bool operator < (int64_t t) const { return *this < BigInt(t); }
bool operator <= (int64_t t) const { return *this <= BigInt(t); }
bool operator > (int64_t t) const { return *this > BigInt(t); }
bool operator >= (int64_t t) const { return *this >= BigInt(t); }
// 0 if |a| == |b|
// -1 if |a| < |b|
// 1 if |a| > |b|
int __compare_abs(const BigInt &b) const {
if (size() != b.size()) {
return size() < b.size() ? -1 : 1;
}
for (int i = (int)size() - 1; i >= 0; i--) {
if ((*this)[i] != b[i]) {
return (*this)[i] < b[i] ? -1 : 1;
}
}
return 0;
}
// -------------------- karatsuba ---------------------
BigInt mul_simple(const BigInt &a, const BigInt &b) {
BigInt res;
res.sign = a.sign * b.sign;
res.digit.resize(a.size() + b.size());
for (int i = 0; i < (int)a.size(); i++) {
uint64_t carry = 0;
for (int j = 0; j < (int)b.size(); j++) {
uint64_t cur = res[i+j] + carry;
cur += 1ull * a[i] * b[j];
res[i+j] = cur % BASE;
carry = cur / BASE;
}
if (carry) res[i+(int)b.size()] += carry;
}
res.trim();
if (res.isZero()) res.sign = 1;
return res;
}
BigInt shifted(int 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) {
if (a.size() < 32 || b.size() < 32) {
return mul_simple(a, b);
}
size_t n = max(a.size(), b.size());
size_t k = n / 2;
BigInt a_low, a_high, b_low, b_high;
int m1 = min(k, a.size()), m2 = min(k, b.size());
a_low.digit.assign(a.digit.begin(), a.digit.begin() + m1);
a_high.digit.assign(a.digit.begin() + m1, a.digit.end());
b_low.digit.assign(b.digit.begin(), b.digit.begin() + m2);
b_high.digit.assign(b.digit.begin() + m2, b.digit.end());
a_low.sign = a_high.sign = b_low.sign = b_high.sign = 1;
a_low.trim(); a_high.trim();
b_low.trim(); b_high.trim();
BigInt z0 = karatsuba(a_low, b_low);
BigInt z1 = karatsuba(a_high, b_high);
BigInt z2 = karatsuba(a_low + a_high, b_low + b_high) - z1 - z0;
BigInt res = z1.shifted(2 * k) + z2.shifted(k) + z0;
res.trim();
res.sign = (a.sign != b.sign ? -1 : 1);
return res;
}
// ------------------------ Div / Mod -----------------------
pair<BigInt, BigInt> divmod(const BigInt &a1, const BigInt &b1) {
assert(b1 != 0); // not divided for 0
ll norm = BASE / (b1.digit.back() + 1);
BigInt a = a1.abs() * norm;
BigInt b = b1.abs() * norm;
BigInt q = 0, r = 0;
q.digit.resize(a.size());
for (int i = a.size() - 1; i >= 0; i--) {
r *= BASE;
r += a[i];
int64_t s1 = r.size() <= b.size() ? 0 : r[b.size()];
int64_t s2 = r.size() <= b.size() - 1 ? 0 : r[b.size() - 1];
int64_t d = (BASE * s1 + s2) / b.digit.back();
if (d >= BASE) {
d = BASE - 1;
}
r -= b * d;
while (r < 0) {
r += b, --d;
}
q[i] = d;
}
q.sign = a1.sign * b1.sign;
r.sign = a1.sign;
q.trim(); r.trim();
BigInt remainder;
remainder.digit.resize(r.size());
int64_t carry = 0;
for (int i = (int)r.size() - 1; i >= 0; i--) {
int64_t cur = r[i] + carry * BASE;
remainder[i] = cur / norm;
carry = cur % norm;
}
remainder.sign = r.sign;
remainder.trim();
auto res = make_pair(q, remainder);
return res;
}
// ------------------------- Misc ---------------------------
size_t size() const { return digit.size(); }
bool isZero() const { return digit.empty(); }
void trim() {
while (!digit.empty() && !digit.back()) {
digit.pop_back();
}
if (digit.empty()) sign = 1;
}
BigInt abs() const { BigInt res = *this; res.sign = 1; return res; }
string toString() const {
ostringstream oss;
oss << *this;
return oss.str();
}
// only support b >= 0, if b < 0 need to implement modulo inverse
friend BigInt pow(const BigInt &a, const BigInt &b, ll mod) { return pow(a, b, BigInt(mod)); }
friend BigInt pow(const BigInt &a, const BigInt &b, const BigInt &mod) {
BigInt x(a), y(b), res(1);
while (y != 0) {
if (y[0] % 2 == 1) res = res * x % mod;
x = x * x % mod;
y /= 2;
}
return res;
}
friend BigInt pow(const BigInt &a, const BigInt &b) {
BigInt x(a), y(b), res(1);
while (y != 0) {
if (y[0] % 2 == 1) res = res * x;
x = x * x;
y /= 2;
}
return res;
}
friend BigInt __gcd(const BigInt &a, const BigInt &b) {
if (b == 0) return a.abs();
return __gcd(b, a % b);
}
friend BigInt __lcm(const BigInt &a, const BigInt &b) {
if (a == 0 || b == 0) return BigInt(0);
return (a / __gcd(a, b) * b).abs();
}
// safe sqrt for long long and BigInt
friend BigInt sqrt(const BigInt &a1) {
BigInt a = a1;
while (a.digit.empty() || a.size() % 2 == 1) {
a.digit.push_back(0);
}
int n = a.size();
int firstDigit = (int) sqrt((double) a[n - 1] * BASE + a[n - 2]);
int norm = BASE / (firstDigit + 1);
a = a * norm * norm;
while (a.digit.empty() || a.size() % 2 == 1) {
a.digit.push_back(0);
}
BigInt r = 1ll * a[n - 1] * BASE + a[n - 2];
firstDigit = (int) sqrt((double) a[n - 1] * BASE + a[n - 2]);
int q = firstDigit;
BigInt res;
for (int j = n / 2 - 1; j >= 0; j--) {
for (; ; --q) {
BigInt r1 = (r - (res * 2 * BigInt(BASE) + q) * q) * BigInt(BASE) * BigInt(BASE);
r1 += (j > 0 ? 1ll * a[2 * j - 1] * BASE + a[2 * j - 2] : 0);
if (r1 >= 0) {
r = r1;
break;
}
}
res *= BASE;
res += q;
if (j > 0) {
int d1 = res.size() + 2 < r.size() ? r[res.size() + 2] : 0;
int d2 = res.size() + 1 < r.size() ? r[res.size() + 1] : 0;
int d3 = res.size() < r.size() ? r[res.size()] : 0;
q = (1ll * d1 * BASE * BASE + 1ll * d2 * BASE + d3) / (firstDigit * 2);
}
}
res.trim();
return res / norm;
}
// ---------------------- Input Output ---------------------
/* only use for decimal number */
void read(const string &s) {
if (s.empty()) { *this = 0; return; }
sign = (s[0] == '-' ? -1 : 1);
digit.clear();
int pos = (s[0] == '-' ? 1 : 0);
for (int i = (int)s.size() - 1; i >= pos; i -= BASE_DIGITS) {
int x = 0;
int k = max(pos, i - BASE_DIGITS + 1);
for (int j = k; j <= i; j++) {
x = x * 10 + (s[j] - '0');
}
digit.push_back(x);
}
trim();
}
friend istream &operator >> (istream &in, BigInt &a) {
string s; in >> s;
a.read(s);
return in;
}
friend ostream &operator << (ostream &out, const BigInt &a) {
if (a.sign == -1 && !a.isZero()) out << '-';
out << (a.digit.empty() ? 0 : a.digit.back());
char old = out.fill('0');
for (int i = (int)a.size() - 2; i >= 0; i--)
out << setw(BASE_DIGITS) << a[i];
out.fill(old);
return out;
}
};
#line 5 "Big_Integer/Yosupo/Unit_test_math.test.cpp"
using B = BigInt<>; // D = 9
using B4 = BigInt<4>; // cung logic, khac limb -> doi chieu cheo
using B1 = BigInt<1>;
string i128str(__int128 v) {
if (v == 0) return "0";
bool neg = v < 0; if (neg) v = -v;
string s;
while (v) { s += char('0' + int(v % 10)); v /= 10; }
if (neg) s += '-';
reverse(s.begin(), s.end());
return s;
}
// so sanh hai so nguyen dang chuoi, doc lap hoan toan voi BigInt
int refCmp(string x, string y) {
int sx = 1, sy = 1;
if (x[0] == '-') { sx = -1; x = x.substr(1); }
if (y[0] == '-') { sy = -1; y = y.substr(1); }
x.erase(0, min(x.find_first_not_of('0'), x.size() - 1));
y.erase(0, min(y.find_first_not_of('0'), y.size() - 1));
if (x == "0") sx = 0;
if (y == "0") sy = 0;
if (sx != sy) return sx < sy ? -1 : 1;
int c = x.size() != y.size() ? (x.size() < y.size() ? -1 : 1)
: (x == y ? 0 : (x < y ? -1 : 1));
return sx >= 0 ? c : -c;
}
string rndDigits(int n, mt19937 &g, bool neg = false) {
string s;
if (neg) s += '-';
s += char('1' + g() % 9);
for (int i = 1; i < n; i++) s += char('0' + g() % 10);
return s;
}
void solve() {
mt19937 g(20260726);
// ---------- 1. khoi tao va in ra ----------
assert(B().toString() == "0");
assert(B(0).toString() == "0");
assert(B("0").toString() == "0");
assert(B("-0").toString() == "0");
assert(B("0000123").toString() == "123");
assert(B("-0000123").toString() == "-123");
assert(B(LLONG_MAX).toString() == "9223372036854775807");
assert(B(LLONG_MIN + 1).toString() == "-9223372036854775807");
for (int t = 0; t < 300; t++) {
string s = rndDigits(1 + g() % 60, g, g() & 1);
assert(B(s).toString() == s);
assert(B4(s).toString() == s);
assert(B1(s).toString() == s);
}
// ---------- 2. so 0 chi co MOT bieu dien ----------
vector<B> zeros = {B(), B(0), B("0"), B("-0"), B(5) - B(5), B(0) * B(-7)};
{ B t(-10); t %= 5LL; zeros.push_back(t); }
{ B t(-10); t /= 3LL; t /= 4LL; zeros.push_back(t); }
for (const B &z : zeros) {
assert(z.isZero() && z.sign == 1 && z.toString() == "0");
for (const B &w : zeros)
assert(z == w && !(z < w) && !(z > w) && z <= w && z >= w);
}
// ---------- 3. so hoc doi chieu long long ----------
vector<ll> smalls;
for (ll x = -40; x <= 40; x++) smalls.push_back(x);
for (ll x : {999999998LL, 999999999LL, 1000000000LL, 1000000001LL,
-1000000000LL, 123456789012345LL, -987654321098765LL}) smalls.push_back(x);
for (ll a : smalls) for (ll b : smalls) {
B A(a), B_(b);
assert((A + B_) == B(a + b));
assert((A - B_) == B(a - b));
assert((A * B_).toString() == i128str((__int128)a * b));
assert((A < B_) == (a < b) && (A > B_) == (a > b) && (A == B_) == (a == b));
assert((A <= B_) == (a <= b) && (A >= B_) == (a >= b) && (A != B_) == (a != b));
assert((A < b) == (a < b) && (A == b) == (a == b) && (A >= b) == (a >= b));
if (b != 0) {
assert((A / B_) == B(a / b)); // chat ve 0, giong C++
assert((A % B_) == B(a % b));
assert(A / B_ * B_ + A % B_ == A); // bat bien
}
if (b != 0 && llabs(b) <= 1000000000LL) {
B q = A, r = A;
q /= b; r %= b;
assert(q == B(a / b) && r == B(a % b));
}
}
// ---------- 3b. so sanh ky: nhieu limb, co limb bang 0 ----------
{
vector<string> v = {"0", "-0", "1", "-1", "999999999", "-999999999",
"1000000000", "-1000000000", "1000000005", "-1000000005",
"1000000000000000000", "-1000000000000000000",
"1000000000000000001", "-1000000000000000001",
"2000000000", "-2000000000", "999999999999999999", "-999999999999999999",
"1000000000000000000000000000", "-1000000000000000000000000000",
"1000000000000000000000000001", "-1000000000000000000000000001"};
for (int t = 0; t < 200; t++) {
string s;
int limbs = 1 + g() % 4;
for (int i = 0; i < limbs; i++) {
int d = (g() % 3 == 0) ? 0 : (int)(g() % 1000000000);
string p = to_string(d);
s += string(9 - p.size(), '0') + p;
}
s.erase(0, min(s.find_first_not_of('0'), s.size() - 1));
v.push_back(s);
v.push_back("-" + s);
}
for (const string &x : v) for (const string &y : v) {
int c = refCmp(x, y);
B a(x), b(y);
assert((a < b) == (c < 0));
assert((a > b) == (c > 0));
assert((a == b) == (c == 0));
assert((a <= b) == (c <= 0));
assert((a >= b) == (c >= 0));
assert((a != b) == (c != 0));
}
}
// ---------- 4. don nguyen, tang giam ----------
for (ll x : {-7LL, -1LL, 0LL, 1LL, 9LL}) {
B a(x);
assert((-a) == B(-x) && (+a) == B(x) && (-(-a)) == a);
B b = a; assert((++b) == B(x + 1) && b == B(x + 1));
B c = a; assert((c++) == B(x) && c == B(x + 1));
B d = a; assert((--d) == B(x - 1));
B e = a; assert((e--) == B(x) && e == B(x - 1));
}
assert((-B(0)).sign == 1 && (-B(0)).toString() == "0");
// ---------- 5. int op BigInt (friend) ----------
assert((100LL + B(23)) == B(123));
assert((100LL - B(23)) == B(77));
assert((100LL * B(23)) == B(2300));
assert((100LL / B(23)) == B(4));
assert((100LL % B(23)) == B(8));
// ---------- 6. so lon: doi chieu cheo D=9 / D=4 / D=1 ----------
for (int t = 0; t < 40; t++) {
int la = 50 + g() % 700, lb = 50 + g() % 700; // vuot nguong karatsuba
string sa = rndDigits(la, g, g() & 1), sb = rndDigits(lb, g, false);
B a(sa), b(sb);
B4 a4(sa), b4(sb);
B1 a1(sa), b1(sb);
assert((a + b).toString() == (a4 + b4).toString());
assert((a - b).toString() == (a4 - b4).toString());
assert((a * b).toString() == (a4 * b4).toString());
assert((a / b).toString() == (a4 / b4).toString());
assert((a % b).toString() == (a4 % b4).toString());
assert((a * b).toString() == (a1 * b1).toString());
assert(a / b * b + a % b == a);
}
// ---------- 7. dong nhat thuc so lon ----------
for (int k : {1, 5, 20, 100, 400}) {
B p = pow(B(10), B(k));
assert(p.toString() == "1" + string(k, '0'));
assert((p - 1) * (p + 1) == pow(B(10), B(2 * k)) - 1);
B a = p - 1, b = p + 7;
assert((a + b) * (a + b) == a * a + 2 * (a * b) + b * b);
assert((a - b) * (a + b) == a * a - b * b);
}
B f1(1); for (int i = 1; i <= 100; i++) f1 *= i;
B f2(1); for (int i = 100; i >= 1; i--) f2 = f2 * i;
assert(f1 == f2);
assert(f1.toString().size() == 158); // 100! co 158 chu so
assert(f1 % 101 == B(100)); // wilson: 100! = -1 (mod 101)
// ---------- 8. sqrt ----------
for (ll x = 0; x <= 400; x++) {
assert(sqrt(B(x * x)) == B(x));
if (x) assert(sqrt(B(x * x + x)) == B(x));
if (x) assert(sqrt(B(x * x - 1)) == B(x - 1));
}
for (int t = 0; t < 30; t++) {
B a(rndDigits(1 + g() % 60, g)), r = sqrt(a);
assert(r * r <= a && (r + 1) * (r + 1) > a);
}
// ---------- 9. pow ----------
for (ll a = 2; a <= 12; a++) for (ll e = 0; e <= 15; e++) {
ll p = 1; for (ll i = 0; i < e; i++) p *= a;
assert(pow(B(a), B(e)) == B(p));
assert(pow(B(a), B(e), 1000000007LL) == B(p % 1000000007));
}
assert(pow(B(7), B(0)) == B(1));
assert(pow(B(0), B(5)) == B(0));
for (ll a : {2LL, 3LL, 123456LL}) // fermat
assert(pow(B(a), B(1000000006LL), 1000000007LL) == B(1));
// ---------- 10. gcd / lcm ----------
for (ll a = -30; a <= 30; a++) for (ll b = -30; b <= 30; b++) {
B G = __gcd(B(a), B(b));
assert(G == B(__gcd(llabs(a), llabs(b))) && G >= B(0));
B L = __lcm(B(a), B(b));
if (a == 0 || b == 0) assert(L == B(0));
else assert(L == B(llabs(a) / __gcd(llabs(a), llabs(b)) * llabs(b)));
}
{
B gg = pow(B(10), B(30)) + 7;
assert(__gcd(B(999983) * gg, B(1000003) * gg) == gg);
}
// ---------- 11. abs / isZero / size ----------
assert(B(-123).abs() == B(123) && B(0).abs().sign == 1);
assert(B(0).isZero() && !B(1).isZero());
assert(B(0).size() == 0 && B("999999999").size() == 1 && B("1000000000").size() == 2);
// ---------- 12. stream khong bi ban ----------
{ ostringstream os; os << B("1000000000000000000") << setw(5) << 42;
assert(os.str() == "1000000000000000000 42"); }
{ istringstream is("-123456789012345678901234567890"); B a; is >> a;
assert(a.toString() == "-123456789012345678901234567890"); }
ll a, b; cin >> a >> b;
cout << a + b << '\n';
}