高精度
以下均为压位高精度 高精度除高精度以二分法求
以下均含divide带余数除法 TODO：FFT高精度除高精度
快速傅里叶加速乘法
Code
namespace FFT {
using cpx = complex<double>;
const double PI = acos(-1);
vector<cpx> roots = {{0, 0}, {1, 0}};
void ensure_capacity(int min_capacity) {
for (int len = roots.size(); len < min_capacity; len <<= 1) {
for (int i = len >> 1; i < len; i++) {
roots.emplace_back(roots[i]);
double angle = 2 * PI * (2 * i + 1 - len) / (len << 1);
roots.emplace_back(cos(angle), sin(angle));
}
}
}
void fft(vector<cpx>& z, bool inverse) {
int n = z.size();
ensure_capacity(n);
for (unsigned i = 1, j = 0, bit; i < n; i++) {
for (bit = n >> 1; j >= bit; bit >>= 1) j -= bit;
j += bit;
if (i < j) swap(z[i], z[j]);
}
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i < n; i += len << 1) {
for (int j = 0; j < len; j++) {
cpx root = inverse ? conj(roots[j + len]) : roots[j + len];
cpx u = z[i + j];
cpx v = z[i + j + len] * root;
z[i + j] = u + v;
z[i + j + len] = u - v;
}
}
}
if (inverse)
for (int i = 0; i < n; i++) z[i] /= n;
}
vector<int> multiply_bigint(const vector<int>& a, const vector<int>& b, int base) {
int need = a.size() + b.size(), n = 1;
while (n < need) n <<= 1;
vector<cpx> p(n);
for (size_t i = 0; i < n; i++) p[i] = cpx(i < a.size() ? a[i] : 0, i < b.size() ? b[i] : 0);
fft(p, false);
vector<cpx> ab(n);
cpx r(0, -0.25);
for (int i = 0, j; i < n; i++) j = (n - i) & (n - 1), ab[i] = (p[i] * p[i] - conj(p[j] * p[j])) * r;
fft(ab, true);
vector<int> result(need);
long long carry = 0;
for (int i = 0; i < need; i++) {
long long d = (long long)(ab[i].real() + 0.5) + carry;
carry = d / base;
result[i] = d % base;
}
return result;
}
constexpr int fft_BASE = (int)1e4; // fft_base^2 * n / fft_WS <= 10^15 for double
constexpr int fft_WS = 4;
} // namespace FFT
struct ubigint : public vector<int> {
const static int BASE = (int)1e4;
const static int WS = 4; // change with BASE
static vector<int> convert_base(const vector<int>::const_iterator& beg, size_t sz, int old_digits, int new_digits) {
if (old_digits == new_digits) return vector<int>(beg, beg + sz);
vector<int> 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;
vector<int> res;
long long cur = 0;
int cur_digits = 0;
for (size_t i = 0; i < sz; ++i) {
cur += 1ll * *(beg + i) * p[cur_digits];
cur_digits += old_digits;
while (cur_digits >= new_digits) {
res.emplace_back(cur % p[new_digits]);
cur /= p[new_digits];
cur_digits -= new_digits;
}
}
res.emplace_back((int)cur);
while (!res.empty() && !res.back()) res.pop_back();
return res;
}
ubigint() {}
ubigint(int t) : vector<int>(1, t) {}
ubigint(long long t) {
while (t) emplace_back(t % BASE);
}
ubigint(const vector<int>& v) : vector<int>(v) {}
ubigint(string s) {
for (int i = s.size() - 1, j, t; i >= 0; i -= WS) {
for (j = max(0, i - WS + 1), t = 0; j <= i; ++j) t = (t * 10 + (s[j] - '0'));
emplace_back(t);
}
}
unsigned int digits() const {
if (isZero()) return 1;
unsigned int d = (size() - 1u) * WS;
int x = back();
while (x) ++d, x /= 10;
return d;
}
const bool isZero() const { return empty() or (size() == 1u and !front()); }
int const& operator[](const int n) const { return (n < size()) ? *(cbegin() + n) : (int const&)0; }
int& operator[](const int n) { return *(begin() + n); }
operator string() {
if (isZero()) return "0";
string ans;
stringstream ss;
ss << back();
for (int i = (int)size() - 2; ~i; --i) ss << setw(WS) << setfill('0') << *(begin() + i);
ss >> ans;
return ans;
}
friend void read(ubigint& a) {
string s;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) s.push_back(c), c = getchar();
a = ubigint(s);
}
friend void print(const ubigint& a) {
if (a.isZero()) return (void)putchar('0');
printf("%d", a.back());
for (int i = (int)a.size() - 2; ~i; --i) printf("%0*d", WS, a[i]);
}
friend bool operator==(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return 0;
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] != b[i]) return 0;
return 1;
}
friend bool operator!=(ubigint const& a, ubigint const& b) { return !(a == b); }
friend bool operator<(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = (int)a.size() - 1; ~i; --i)
if (a[i] != b[i]) return a[i] < b[i];
return 0;
}
friend bool operator>(ubigint const& a, ubigint const& b) { return b < a; }
friend bool operator<=(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = (int)a.size() - 1; ~i; --i)
if (a[i] != b[i]) return a[i] < b[i];
return 1;
}
friend bool operator>=(ubigint const& a, ubigint const& b) { return b <= a; }
friend ubigint operator+(ubigint const& a, ubigint const& b) {
ubigint c = a;
c.resize(max(a.size(), b.size()) + 1);
for (int i = 0, en = b.size(); i < en; ++i) {
c[i] += b[i];
if (c[i] >= BASE) c[i] -= BASE, ++c[i + 1];
}
for (int i = b.size(), en = c.size() - 1; i < en; ++i)
if (c[i] >= BASE) c[i] -= BASE, ++c[i + 1];
if (!c.back()) c.pop_back();
return c;
}
friend ubigint operator-(ubigint const& a, ubigint const& b) {
ubigint c = a;
for (int i = 0, en = b.size(); i < en; ++i) {
c[i] -= b[i];
if (c[i] < 0) c[i] += BASE, --c[i + 1];
}
for (int i = b.size(), en = c.size(); i < en; ++i) {
if (c[i] < 0)
c[i] += BASE, --c[i + 1];
else
break;
}
while (c.size() > 1u && !c.back()) c.pop_back();
return c;
}
friend ubigint operator*(ubigint const& a, int o) {
if (!o or a.isZero()) return 0;
int n = a.size();
ubigint c;
c.resize(n);
long long carry = 0;
for (int i = 0; i < n; ++i) {
carry += (long long)a[i] * o;
c[i] = carry % BASE;
carry /= BASE;
}
if (carry) c.emplace_back(carry);
return c;
}
friend ubigint operator*(ubigint const& a, ubigint const& b) {
if (a.isZero() or b.isZero()) return 0;
ubigint res(FFT::multiply_bigint(convert_base(a.begin(), a.size(), WS, FFT::fft_WS), convert_base(b.cbegin(), b.size(), WS, FFT::fft_WS), FFT::fft_BASE));
res = convert_base(res.begin(), res.size(), FFT::fft_WS, WS);
while (!res.empty() and !res.back()) res.pop_back();
return res;
}
friend ubigint operator/(ubigint const& a, ubigint const& b) {
assert(!b.isZero());
if (a.size() < b.size()) return 0;
ubigint c, d;
c.assign(a.end() - b.size() + 1, a.end());
for (int i = a.size() - b.size(); ~i; --i) {
c.insert(c.begin(), *(a.begin() + i));
long long t = (c.size() > b.size()) ? ((long long)c.back() * BASE + *(c.crbegin() + 1)) : c.back();
int l = (t / (b.back() + 1)), r = ((t + 1) / b.back()), mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (b * mid <= c)
l = mid;
else
r = mid - 1;
}
c -= b * l;
if (!c.back()) c.pop_back();
d.emplace_back(l);
}
reverse(d.begin(), d.end());
if (d.size() > 1u && !d.back()) d.pop_back();
return d;
}
friend ubigint divide(ubigint const& a, ubigint const& b, ubigint& c) {
assert(!b.isZero());
if (a.size() < b.size() or a.isZero()) return c = a, 0;
ubigint d;
c.assign(a.end() - b.size() + 1, a.end());
for (int i = a.size() - b.size(); ~i; --i) {
c.insert(c.begin(), *(a.begin() + i));
long long t = (c.size() > b.size()) ? ((long long)c.back() * BASE + *(c.crbegin() + 1)) : c.back();
int l = (t / (b.back() + 1)), r = ((t + 1) / b.back()), mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (b * mid <= c)
l = mid;
else
r = mid - 1;
}
c -= b * l;
if (!c.back()) c.pop_back();
d.emplace_back(l);
}
reverse(d.begin(), d.end());
if (d.size() > 1u && !d.back()) d.pop_back();
return d;
}
friend ubigint operator%(ubigint const& a, ubigint const& b) { return a - a / b * b; }
friend ubigint const& operator+=(ubigint& a, ubigint const& b) { return a = a + b; }
friend ubigint const& operator-=(ubigint& a, ubigint const& b) { return a = a - b; }
friend ubigint const& operator*=(ubigint& a, int const& b) { return a = a * b; }
friend ubigint const& operator*=(ubigint& a, ubigint const& b) { return a = a * b; }
friend ubigint const& operator/=(ubigint& a, ubigint const& b) { return a = a / b; }
friend ubigint const& operator%=(ubigint& a, ubigint const& b) { return a = a % b; }
};
struct bigint {
bool f;
ubigint t;
bigint() : f(0) {}
bigint(int t) : f(t < 0), t(ubigint(abs(t))) {}
bigint(long long x) : f(x < 0) {
while (x) t.emplace_back(x);
}
bigint(bool f, ubigint t) : f(f), t(t) {}
bigint(const vector<int>& a) : t(a) {}
unsigned int digits() const { return t.digits(); }
const bool isZero() const { return t.isZero(); }
int const& operator[](const int n) const { return (n < t.size()) ? *(t.cbegin() + n) : (int const&)0; }
int& operator[](const int n) { return *(t.begin() + n); }
operator string() {
if (t.isZero()) return "0";
string ans;
stringstream ss;
if (f) ss << '-';
ss << t.back();
for (int i = (int)t.size() - 2; ~i; --i) ss << setw(t.WS) << setfill('0') << t[i];
ss >> ans;
return ans;
}
friend void read(bigint& a) {
a.f = 0;
string s;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') a.f = 1;
while (isdigit(c)) s.push_back(c), c = getchar();
a.t = ubigint(s);
}
friend void print(const bigint& a) {
if (a.t.isZero()) return (void)putchar('0');
if (a.f) putchar('-');
print(a.t);
}
friend bigint abs(bigint const& a) { return bigint(0, a.t); }
friend bool operator==(bigint const& a, bigint const& b) { return (a.f == b.f) && (a.t == b.t); }
friend bool operator!=(bigint const& a, bigint const& b) { return !(a == b); }
friend bool operator<(bigint const& a, bigint const& b) {
if (a.f != b.f) return a.f;
return a.f ? a.t > b.t : a.t < b.t;
}
friend bool operator>(bigint const& a, bigint const& b) { return b < a; }
friend bool operator<=(bigint const& a, bigint const& b) {
if (a.f != b.f) return a.f;
return a.f ? a.t >= b.t : a.t <= b.t;
}
friend bool operator>=(bigint const& a, bigint const& b) { return b <= a; }
friend bigint operator-(bigint const& a) { return bigint(!a.f, a.t); }
friend bigint operator+(bigint const& a, bigint const& b) {
if (a.f == b.f) return bigint(a.f, a.t + b.t);
if (a.t > b.t) return bigint(a.f, a.t - b.t);
if (a.t < b.t) return bigint(b.f, b.t - a.t);
return 0;
}
friend bigint operator-(bigint const& a, bigint const& b) {
if (a.f == b.f) {
if (a.t > b.t) return bigint(a.f, a.t - b.t);
if (a.t < b.t) return bigint(!a.f, b.t - a.t);
return 0;
}
return bigint(a.f, a.t + b.t);
}
friend bigint operator*(bigint const& a, bigint const& b) { return bigint(a.f ^ b.f, a.t * b.t); }
friend bigint operator*(bigint const& a, int const& b) { return bigint(a.f ^ (b < 0), a.t * b); }
friend bigint divide(bigint const& a, bigint const& b, bigint& c) { return bigint(a.f ^ b.f, divide(a.t, b.t, (c.f = a.f, c.t))); }
friend bigint operator/(bigint const& a, bigint const& b) { return bigint(a.f ^ b.f, a.t / b.t); }
friend bigint operator%(bigint const& a, bigint const& b) { return bigint(a.f, a.t % b.t); }
friend bigint const& operator+=(bigint& a, bigint const& b) { return a = a + b; }
friend bigint const& operator-=(bigint& a, bigint const& b) { return a = a - b; }
friend bigint const& operator*=(bigint& a, int const& b) { return a = a * b; }
friend bigint const& operator*=(bigint& a, bigint const& b) { return a = a * b; }
friend bigint const& operator/=(bigint& a, bigint const& b) { return a = a / b; }
friend bigint const& operator%=(bigint& a, bigint const& b) { return a = a % b; }
};
// don't close ios_base::sync_with_stdio
不加速
编译器无__int128(压1~8位)
Code
struct ubigint : public vector<int> {
const static int BASE = (int)1e8;
const static int WS = 8; // change with BASE
ubigint() {}
ubigint(int t) : vector<int>(1, t) {}
ubigint(long long x) {
while (x) emplace_back(x);
}
ubigint(const vector<int>& a) : vector<int>(a) {}
ubigint(string s) {
for (int i = s.size() - 1, j, t; i >= 0; i -= WS) {
for (j = max(0, i - WS + 1), t = 0; j <= i; ++j) t = (t * 10 + (s[j] - '0'));
emplace_back(t);
}
}
unsigned int digits() const {
if (isZero()) return 1;
unsigned int d = (size() - 1u) * WS;
int x = back();
while (x) ++d, x /= 10;
return d;
}
const bool isZero() const { return empty() or (size() == 1u and !front()); }
int const& operator[](const int n) const { return (n < size()) ? *(cbegin() + n) : (int const&)0; }
int& operator[](const int n) { return *(begin() + n); }
operator string() {
if (isZero()) return "0";
string ans;
stringstream ss;
ss << back();
for (int i = (int)size() - 2; ~i; --i) ss << setw(WS) << setfill('0') << *(begin() + i);
ss >> ans;
return ans;
}
friend void read(ubigint& a) {
string s;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) s.push_back(c), c = getchar();
a = ubigint(s);
}
friend void print(const ubigint& a) {
if (a.isZero()) return (void)putchar('0');
printf("%d", a.back());
for (int i = (int)a.size() - 2; ~i; --i) printf("%0*d", WS, a[i]);
}
friend bool operator==(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return 0;
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] != b[i]) return 0;
return 1;
}
friend bool operator!=(ubigint const& a, ubigint const& b) { return !(a == b); }
friend bool operator<(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = (int)a.size() - 1; ~i; --i)
if (a[i] != b[i]) return a[i] < b[i];
return 0;
}
friend bool operator>(ubigint const& a, ubigint const& b) { return b < a; }
friend bool operator<=(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = (int)a.size() - 1; ~i; --i)
if (a[i] != b[i]) return a[i] < b[i];
return 1;
}
friend bool operator>=(ubigint const& a, ubigint const& b) { return b <= a; }
friend ubigint operator+(ubigint const& a, ubigint const& b) {
ubigint c = a;
c.resize(max(a.size(), b.size()) + 1);
for (int i = 0, en = b.size(); i < en; ++i) {
c[i] += b[i];
if (c[i] >= BASE) c[i] -= BASE, ++c[i + 1];
}
for (int i = b.size(), en = c.size() - 1; i < en; ++i)
if (c[i] >= BASE) c[i] -= BASE, ++c[i + 1];
if (!c.back()) c.pop_back();
return c;
}
friend ubigint operator-(ubigint const& a, ubigint const& b) {
ubigint c = a;
for (int i = 0, en = b.size(); i < en; ++i) {
c[i] -= b[i];
if (c[i] < 0) c[i] += BASE, --c[i + 1];
}
for (int i = b.size(), en = c.size(); i < en; ++i) {
if (c[i] < 0)
c[i] += BASE, --c[i + 1];
else
break;
}
while (c.size() > 1u && !c.back()) c.pop_back();
return c;
}
friend ubigint operator*(ubigint const& a, int o) {
if (!o or a.isZero()) return 0;
int n = a.size();
ubigint c;
c.resize(n);
long long carry = 0;
for (int i = 0; i < n; ++i) {
carry += (long long)a[i] * o;
c[i] = carry % BASE;
carry /= BASE;
}
if (carry) c.emplace_back(carry);
return c;
}
friend ubigint operator*(ubigint const& a, ubigint const& b) {
if (a.isZero() || b.isZero()) return 0;
int sa = a.size(), sb = b.size();
vector<long long> t(sa + sb);
for (int i = 0; i < sa; ++i)
for (int j = 0; j < sb; ++j) t[i + j] += (long long)a[i] * b[j];
for (int i = 0, en = t.size() - 1; i < en; ++i) t[i + 1] += t[i] / BASE, t[i] %= BASE;
if (!t.back()) t.pop_back();
ubigint c;
c.resize(t.size());
for (int i = 0, en = t.size(); i < en; ++i) c[i] = (int)t[i];
return c;
}
friend ubigint operator/(ubigint const& a, ubigint const& b) {
assert(!b.isZero());
if (a.size() < b.size()) return 0;
ubigint c, d;
c.assign(a.end() - b.size() + 1, a.end());
for (int i = a.size() - b.size(); ~i; --i) {
c.insert(c.begin(), *(a.begin() + i));
long long t = (c.size() > b.size()) ? ((long long)c.back() * BASE + *(c.crbegin() + 1)) : c.back();
int l = (t / (b.back() + 1)), r = ((t + 1) / b.back()), mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (b * mid <= c)
l = mid;
else
r = mid - 1;
}
c -= b * l;
if (!c.back()) c.pop_back();
d.emplace_back(l);
}
reverse(d.begin(), d.end());
if (d.size() > 1u && !d.back()) d.pop_back();
return d;
}
friend ubigint divide(ubigint const& a, ubigint const& b, ubigint& c) {
assert(!b.isZero());
if (a.size() < b.size() or a.isZero()) return c = a, 0;
ubigint d;
c.assign(a.end() - b.size() + 1, a.end());
for (int i = a.size() - b.size(); ~i; --i) {
c.insert(c.begin(), *(a.begin() + i));
long long t = (c.size() > b.size()) ? ((long long)c.back() * BASE + *(c.crbegin() + 1)) : c.back();
int l = (t / (b.back() + 1)), r = ((t + 1) / b.back()), mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (b * mid <= c)
l = mid;
else
r = mid - 1;
}
c -= b * l;
if (!c.back()) c.pop_back();
d.emplace_back(l);
}
reverse(d.begin(), d.end());
if (d.size() > 1u && !d.back()) d.pop_back();
return d;
}
friend ubigint operator%(ubigint const& a, ubigint const& b) { return a - a / b * b; }
friend ubigint const& operator+=(ubigint& a, ubigint const& b) { return a = a + b; }
friend ubigint const& operator-=(ubigint& a, ubigint const& b) { return a = a - b; }
friend ubigint const& operator*=(ubigint& a, int const& b) { return a = a * b; }
friend ubigint const& operator*=(ubigint& a, ubigint const& b) { return a = a * b; }
friend ubigint const& operator/=(ubigint& a, ubigint const& b) { return a = a / b; }
friend ubigint const& operator%=(ubigint& a, ubigint const& b) { return a = a % b; }
};
struct bigint {
bool f;
ubigint t;
bigint() : f(0) {}
bigint(int t) : f(t < 0), t(ubigint(abs(t))) {}
bigint(long long x) : f(x < 0) {
while (x) t.emplace_back(x);
}
bigint(const vector<int>& a) : t(a) {}
bigint(bool f, ubigint t) : f(f), t(t) {}
unsigned int digits() const { return t.digits(); }
const bool isZero() const { return t.isZero(); }
int const& operator[](const int n) const { return (n < t.size()) ? *(t.cbegin() + n) : (int const&)0; }
int& operator[](const int n) { return *(t.begin() + n); }
operator string() {
if (t.isZero()) return "0";
string ans;
stringstream ss;
if (f) ss << '-';
ss << t.back();
for (int i = (int)t.size() - 2; ~i; --i) ss << setw(t.WS) << setfill('0') << t[i];
ss >> ans;
return ans;
}
friend void read(bigint& a) {
a.f = 0;
string s;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') a.f = 1;
while (isdigit(c)) s.push_back(c), c = getchar();
a.t = ubigint(s);
}
friend void print(const bigint& a) {
if (a.t.isZero()) return (void)putchar('0');
if (a.f) putchar('-');
print(a.t);
}
friend bigint abs(bigint const& a) { return bigint(0, a.t); }
friend bool operator==(bigint const& a, bigint const& b) { return (a.f == b.f) && (a.t == b.t); }
friend bool operator!=(bigint const& a, bigint const& b) { return !(a == b); }
friend bool operator<(bigint const& a, bigint const& b) {
if (a.f != b.f) return a.f;
return a.f ? a.t > b.t : a.t < b.t;
}
friend bool operator>(bigint const& a, bigint const& b) { return b < a; }
friend bool operator<=(bigint const& a, bigint const& b) {
if (a.f != b.f) return a.f;
return a.f ? a.t >= b.t : a.t <= b.t;
}
friend bool operator>=(bigint const& a, bigint const& b) { return b <= a; }
friend bigint operator-(bigint const& a) { return bigint(!a.f, a.t); }
friend bigint operator+(bigint const& a, bigint const& b) {
if (a.f == b.f) return bigint(a.f, a.t + b.t);
if (a.t > b.t) return bigint(a.f, a.t - b.t);
if (a.t < b.t) return bigint(b.f, b.t - a.t);
return 0;
}
friend bigint operator-(bigint const& a, bigint const& b) {
if (a.f == b.f) {
if (a.t > b.t) return bigint(a.f, a.t - b.t);
if (a.t < b.t) return bigint(!a.f, b.t - a.t);
return 0;
}
return bigint(a.f, a.t + b.t);
}
friend bigint operator*(bigint const& a, bigint const& b) { return bigint(a.f ^ b.f, a.t * b.t); }
friend bigint operator*(bigint const& a, int const& b) { return bigint(a.f ^ (b < 0), a.t * b); }
friend bigint divide(bigint const& a, bigint const& b, bigint& c) { return bigint(a.f ^ b.f, divide(a.t, b.t, (c.f = a.f, c.t))); }
friend bigint operator/(bigint const& a, bigint const& b) { return bigint(a.f ^ b.f, a.t / b.t); }
friend bigint operator%(bigint const& a, bigint const& b) { return bigint(a.f, a.t % b.t); }
friend bigint const& operator+=(bigint& a, bigint const& b) { return a = a + b; }
friend bigint const& operator-=(bigint& a, bigint const& b) { return a = a - b; }
friend bigint const& operator*=(bigint& a, int const& b) { return a = a * b; }
friend bigint const& operator*=(bigint& a, bigint const& b) { return a = a * b; }
friend bigint const& operator/=(bigint& a, bigint const& b) { return a = a / b; }
friend bigint const& operator%=(bigint& a, bigint const& b) { return a = a % b; }
// don't close ios_base::sync_with_stdio
};
编译器有__int128(压1~18位)
不知道为什么测试速度不如压8位的
Code
struct ubigint : public vector<long long> {
const static long long BASE = (long long)1e18;
const static int WS = 18; // change with BASE
ubigint() {}
ubigint(long long t) : vector<long long>(1, t) {}
ubigint(const vector<long long>& a) : vector<long long>(a) {}
ubigint(string s) {
for (int i = s.size() - 1, j; i >= 0; i -= WS) {
long long t = 0;
for (j = max(0, i - WS + 1); j <= i; ++j) t = (t * 10ll + (s[j] - '0'));
emplace_back(t);
}
}
unsigned int digits() const {
if (isZero()) return 1;
unsigned int d = (size() - 1u) * WS;
long long x = back();
while (x) ++d, x /= 10ll;
return d;
}
const bool isZero() const { return empty() or (size() == 1u and !front()); }
long long const& operator[](const int n) const { return (n < size()) ? *(cbegin() + n) : (long long const&)0; }
long long& operator[](const int n) { return *(begin() + n); }
operator string() {
if (isZero()) return "0";
string ans;
stringstream ss;
ss << back();
for (int i = (int)size() - 2; ~i; --i) ss << setw(WS) << setfill('0') << *(begin() + i);
ss >> ans;
return ans;
}
friend void read(ubigint& a) {
string s;
char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) s.push_back(c), c = getchar();
a = ubigint(s);
}
friend void print(const ubigint& a) {
if (a.isZero()) return (void)putchar('0');
printf("%lld", a.back());
for (int i = (int)a.size() - 2; ~i; --i) printf("%0*lld", WS, a[i]);
}
friend bool operator==(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return 0;
for (int i = 0; i < (int)a.size(); ++i)
if (a[i] != b[i]) return 0;
return 1;
}
friend bool operator!=(ubigint const& a, ubigint const& b) { return !(a == b); }
friend bool operator<(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = (int)a.size() - 1; ~i; --i)
if (a[i] != b[i]) return a[i] < b[i];
return 0;
}
friend bool operator>(ubigint const& a, ubigint const& b) { return b < a; }
friend bool operator<=(ubigint const& a, ubigint const& b) {
if (a.size() != b.size()) return a.size() < b.size();
for (int i = (int)a.size() - 1; ~i; --i)
if (a[i] != b[i]) return a[i] < b[i];
return 1;
}
friend bool operator>=(ubigint const& a, ubigint const& b) { return b <= a; }
friend ubigint operator+(ubigint const& a, ubigint const& b) {
ubigint c = a;
c.resize(max(a.size(), b.size()) + 1);
for (int i = 0, en = b.size(); i < en; ++i) {
c[i] += b[i];
if (c[i] >= BASE) c[i] -= BASE, ++c[i + 1];
}
for (int i = b.size(), en = c.size() - 1; i < en; ++i)
if (c[i] >= BASE) c[i] -= BASE, ++c[i + 1];
if (!c.back()) c.pop_back();
return c;
}
friend ubigint operator-(ubigint const& a, ubigint const& b) {
ubigint c = a;
for (int i = 0, en = b.size(); i < en; ++i) {
c[i] -= b[i];
if (c[i] < 0ll) c[i] += BASE, --c[i + 1];
}
for (int i = b.size(), en = c.size(); i < en; ++i) {
if (c[i] < 0ll)
c[i] += BASE, --c[i + 1];
else
break;
}
while (c.size() > 1u && !c.back()) c.pop_back();
return c;
}
friend ubigint operator*(ubigint const& a, long long o) {
if (!o or a.isZero()) return 0;
int n = a.size();
ubigint c;
c.resize(n);
__int128_t carry = 0;
for (int i = 0; i < n; ++i) {
carry += (__int128_t)a[i] * o;
c[i] = carry % BASE;
carry /= BASE;
}
if (carry) c.emplace_back(carry);
return c;
}
friend ubigint operator*(ubigint const& a, ubigint const& b) {
if (a.isZero() || b.isZero()) return 0ll;
int sa = a.size(), sb = b.size();
vector<__int128_t> t(sa + sb);
for (int i = 0; i < sa; ++i)
for (int j = 0; j < sb; ++j) t[i + j] += (__int128_t)a[i] * b[j];
for (int i = 0, en = t.size() - 1; i < en; ++i) t[i + 1] += t[i] / BASE, t[i] %= BASE;
if (!t.back()) t.pop_back();
ubigint c;
c.resize(t.size());
for (int i = 0, en = t.size(); i < en; ++i) c[i] = (long long)t[i];
return c;
}
friend ubigint operator/(ubigint const& a, ubigint const& b) {
assert(!b.isZero());
if (a.size() < b.size()) return 0;
ubigint c, d;
c.assign(a.end() - b.size() + 1, a.end());
for (int i = a.size() - b.size(); ~i; --i) {
c.insert(c.begin(), *(a.begin() + i));
__int128_t t = (c.size() > b.size()) ? ((__int128_t)c.back() * BASE + *(c.crbegin() + 1)) : c.back();
long long l = (t / (b.back() + 1ll)), r = ((t + 1) / b.back()), mid;
while (l < r) {
mid = (l + r + 1ll) >> 1;
if (b * mid <= c)
l = mid;
else
r = mid - 1ll;
}
c -= b * l;
if (!c.back()) c.pop_back();
d.emplace_back(l);
}
reverse(d.begin(), d.end());
if (d.size() > 1u && !d.back()) d.pop_back();
return d;
}
friend ubigint divide(ubigint const& a, ubigint const& b, ubigint& c) {
assert(!b.isZero());
if (a.size() < b.size() or a.isZero()) return c = a, 0;
ubigint d;
c.assign(a.end() - b.size() + 1, a.end());
for (int i = a.size() - b.size(); ~i; --i) {
c.insert(c.begin(), *(a.begin() + i));
__int128_t t = (c.size() > b.size()) ? ((__int128_t)c.back() * BASE + *(c.crbegin() + 1)) : c.back();
long long l = (t / (b.back() + 1ll)), r = ((t + 1) / b.back()), mid;
while (l < r) {
mid = (l + r + 1ll) >> 1;
if (b * mid <= c)
l = mid;
else
r = mid - 1ll;
}
c -= b * l;
if (!c.back()) c.pop_back();
d.emplace_back(l);
}
reverse(d.begin(), d.end());
if (d.size() > 1u && !d.back()) d.pop_back();
return d;
}
friend ubigint operator%(ubigint const& a, ubigint const& b) { return a - a / b * b; }
friend ubigint const& operator+=(ubigint& a, ubigint const& b) { return a = a + b; }
friend ubigint const& operator-=(ubigint& a, ubigint const& b) { return a = a - b; }
friend ubigint const& operator*=(ubigint& a, long long const& b) { return a = a * b; }
friend ubigint const& operator*=(ubigint& a, ubigint const& b) { return a = a * b; }
friend ubigint const& operator/=(ubigint& a, ubigint const& b) { return a = a / b; }
friend ubigint const& operator%=(ubigint& a, ubigint const& b) { return a = a % b; }
};
struct bigint {
bool f;
ubigint t;
bigint() : f(0) {}
bigint(long long t) : f(t < 0), t(ubigint(abs(t))) {}
bigint(const vector<long long>& a) : t(a) {}
bigint(bool f, ubigint t) : f(f), t(t) {}
unsigned int digits() const { return t.digits(); }
const bool isZero() const { return t.isZero(); }
long long const& operator[](const int n) const { return (n < t.size()) ? *(t.cbegin() + n) : (long long const&)0; }
long long& operator[](const int n) { return *(t.begin() + n); }
operator string() {
if (t.isZero()) return "0";
string ans;
stringstream ss;
if (f) ss << '-';
ss << t.back();
for (int i = (int)t.size() - 2; ~i; --i) ss << setw(t.WS) << setfill('0') << t[i];
ss >> ans;
return ans;
}
friend void read(bigint& a) {
a.f = 0;
string s;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') a.f = 1;
while (isdigit(c)) s.push_back(c), c = getchar();
a.t = ubigint(s);
}
friend void print(const bigint& a) {
if (a.t.isZero()) return (void)putchar('0');
if (a.f) putchar('-');
print(a.t);
}
friend bigint abs(bigint const& a) { return bigint(0, a.t); }
friend bool operator==(bigint const& a, bigint const& b) { return (a.f == b.f) && (a.t == b.t); }
friend bool operator!=(bigint const& a, bigint const& b) { return !(a == b); }
friend bool operator<(bigint const& a, bigint const& b) {
if (a.f != b.f) return a.f;
return a.f ? a.t > b.t : a.t < b.t;
}
friend bool operator>(bigint const& a, bigint const& b) { return b < a; }
friend bool operator<=(bigint const& a, bigint const& b) {
if (a.f != b.f) return a.f;
return a.f ? a.t >= b.t : a.t <= b.t;
}
friend bool operator>=(bigint const& a, bigint const& b) { return b <= a; }
friend bigint operator-(bigint const& a) { return bigint(!a.f, a.t); }
friend bigint operator+(bigint const& a, bigint const& b) {
if (a.f == b.f) return bigint(a.f, a.t + b.t);
if (a.t > b.t) return bigint(a.f, a.t - b.t);
if (a.t < b.t) return bigint(b.f, b.t - a.t);
return 0;
}
friend bigint operator-(bigint const& a, bigint const& b) {
if (a.f == b.f) {
if (a.t > b.t) return bigint(a.f, a.t - b.t);
if (a.t < b.t) return bigint(!a.f, b.t - a.t);
return 0;
}
return bigint(a.f, a.t + b.t);
}
friend bigint operator*(bigint const& a, bigint const& b) { return bigint(a.f ^ b.f, a.t * b.t); }
friend bigint operator*(bigint const& a, long long const& b) { return bigint(a.f ^ (b < 0), a.t * b); }
friend bigint divide(bigint const& a, bigint const& b, bigint& c) { return bigint(a.f ^ b.f, divide(a.t, b.t, (c.f = a.f, c.t))); }
friend bigint operator/(bigint const& a, bigint const& b) { return bigint(a.f ^ b.f, a.t / b.t); }
friend bigint operator%(bigint const& a, bigint const& b) { return bigint(a.f, a.t % b.t); }
friend bigint const& operator+=(bigint& a, bigint const& b) { return a = a + b; }
friend bigint const& operator-=(bigint& a, bigint const& b) { return a = a - b; }
friend bigint const& operator*=(bigint& a, long long const& b) { return a = a * b; }
friend bigint const& operator*=(bigint& a, bigint const& b) { return a = a * b; }
friend bigint const& operator/=(bigint& a, bigint const& b) { return a = a / b; }
friend bigint const& operator%=(bigint& a, bigint const& b) { return a = a % b; }
// don't close ios_base::sync_with_stdio
};