diff options
| -rw-r--r-- | Math/bigint.cpp | 490 |
1 files changed, 490 insertions, 0 deletions
diff --git a/Math/bigint.cpp b/Math/bigint.cpp new file mode 100644 index 0000000..178fb44 --- /dev/null +++ b/Math/bigint.cpp @@ -0,0 +1,490 @@ +#include <bits/stdc++.h> +#define f first +#define s second +using namespace std; +using ll = long long; +using ii = pair<int, int>; +constexpr int MX = 125; + + +using ll = long long; +using db = long double; // or double, if TL is tight +using str = string; // yay python! + +using pi = pair<int,int>; +using pl = pair<ll,ll>; +using pd = pair<db,db>; + +using vi = vector<int>; +using vb = vector<bool>; +using vl = vector<ll>; +using vd = vector<db>; +using vs = vector<str>; +using vpi = vector<pi>; +using vpl = vector<pl>; +using vpd = vector<pd>; + +#define tcT template<class T +#define tcTU tcT, class U +// ^ lol this makes everything look weird but I'll try it +tcT> using V = vector<T>; +tcT, size_t SZ> using AR = array<T,SZ>; +tcT> using PR = pair<T,T>; + +// pairs +#define mp make_pair +#define f first +#define s second + +// vectors +// oops size(x), rbegin(x), rend(x) need C++17 +#define sz(x) int((x).size()) +#define bg(x) begin(x) +#define all(x) bg(x), end(x) +#define rall(x) x.rbegin(), x.rend() +#define sor(x) sort(all(x)) +#define rsz resize +#define ins insert +#define ft front() +#define bk back() +#define pb push_back +#define eb emplace_back +#define pf push_front +#define rtn return + +#define lb lower_bound +#define ub upper_bound +tcT> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); } + +// loops +#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 rep(a) F0R(_,a) +#define each(a,x) for (auto& a: x) + +const int MOD = 1e9+7; // 998244353; +const ll INF = 1e18; // not too close to LLONG_MAX +const db PI = acos((db)-1); +const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!! +mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); +template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>; + +// bitwise ops +// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html +constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set +constexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until USACO updates ... + return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) +constexpr int p2(int x) { return 1<<x; } +constexpr int msk2(int x) { return p2(x)-1; } + +ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up +ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down + +tcT> bool ckmin(T& a, const T& b) { + return b < a ? a = b, 1 : 0; } // set a = min(a,b) +tcT> bool ckmax(T& a, const T& b) { + return a < b ? a = b, 1 : 0; } + +tcTU> T fstTrue(T lo, T hi, U f) { + hi ++; assert(lo <= hi); // assuming f is increasing + while (lo < hi) { // find first index such that f is true + T mid = lo+(hi-lo)/2; + f(mid) ? hi = mid : lo = mid+1; + } + return lo; +} +tcTU> T lstTrue(T lo, T hi, U f) { + lo --; assert(lo <= hi); // assuming f is decreasing + while (lo < hi) { // find first index such that f is true + T mid = lo+(hi-lo+1)/2; + f(mid) ? lo = mid : hi = mid-1; + } + return lo; +} +tcT> void remDup(vector<T>& v) { // sort and remove duplicates + sort(all(v)); v.erase(unique(all(v)),end(v)); } +tcTU> void erase(T& t, const U& u) { // don't erase + auto it = t.find(u); assert(it != end(t)); + t.erase(it); } // element that doesn't exist from (multi)set + +#define tcTUU tcT, class ...U + +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 + tcT, class = void> struct is_iterable : false_type {}; + tcT> struct is_iterable<T, void_t<decltype(begin(declval<T>())), + decltype(end(declval<T>())) + > + > : true_type {}; + tcT> constexpr bool is_iterable_v = is_iterable<T>::value; + + //////////// is_readable + tcT, class = void> struct is_readable : false_type {}; + tcT> struct is_readable<T, + typename std::enable_if_t< + is_same_v<decltype(cin >> declval<T&>()), istream&> + > + > : true_type {}; + tcT> constexpr bool is_readable_v = is_readable<T>::value; + + //////////// is_printable + // // https://nafe.es/posts/2020-02-29-is-printable/ + tcT, class = void> struct is_printable : false_type {}; + tcT> struct is_printable<T, + typename std::enable_if_t< + is_same_v<decltype(cout << declval<T>()), ostream&> + > + > : true_type {}; + tcT> constexpr bool is_printable_v = is_printable<T>::value; +} + +inline namespace Input { + tcT> constexpr bool needs_input_v = !is_readable_v<T> && is_iterable_v<T>; + tcTUU> void re(T& t, U&... u); + tcTU> void re(pair<T,U>& p); // pairs + + // re: read + tcT> typename enable_if<is_readable_v<T>,void>::type re(T& x) { cin >> x; } // default + tcT> void re(complex<T>& c) { T a,b; re(a,b); c = {a,b}; } // complex + tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i); // ex. vectors, arrays + tcTU> void re(pair<T,U>& p) { re(p.f,p.s); } + tcT> typename enable_if<needs_input_v<T>,void>::type re(T& i) { + each(x,i) re(x); } + tcTUU> void re(T& t, U&... u) { re(t); re(u...); } // read multiple + + // rv: resize and read vectors + void rv(size_t) {} + tcTUU> void rv(size_t N, V<T>& t, U&... u); + template<class...U> void rv(size_t, size_t N2, U&... u); + tcTUU> void rv(size_t N, V<T>& t, U&... u) { + t.rsz(N); re(t); + rv(N,u...); } + template<class...U> void rv(size_t, size_t N2, U&... u) { + rv(N2,u...); } + + // dumb shortcuts to read in ints + void decrement() {} // subtract one from each + tcTUU> 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 { + tcT> constexpr bool needs_output_v = !is_printable_v<T> && is_iterable_v<T>; + + // ts: string representation to print + tcT> typename enable_if<is_printable_v<T>,str>::type ts(T v) { + stringstream ss; ss << fixed << setprecision(15) << v; + return ss.str(); } // default + tcT> str bit_vec(T t) { // bit vector to string + str res = "{"; F0R(i,sz(t)) res += ts(t[i]); + res += "}"; return res; } + str ts(V<bool> v) { return bit_vec(v); } + template<size_t SZ> str ts(bitset<SZ> b) { return bit_vec(b); } // bit vector + tcTU> str ts(pair<T,U> p); // pairs + tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v); // vectors, arrays + tcTU> str ts(pair<T,U> p) { return "("+ts(p.f)+", "+ts(p.s)+")"; } + tcT> typename enable_if<is_iterable_v<T>,str>::type ts_sep(T v, str sep) { + // convert container to string w/ separator sep + bool fst = 1; str res = ""; + for (const auto& x: v) { + if (!fst) res += sep; + fst = 0; res += ts(x); + } + return res; + } + tcT> typename enable_if<needs_output_v<T>,str>::type ts(T v) { + return "{"+ts_sep(v,", ")+"}"; } + + // for nested DS + template<int, class T> typename enable_if<!needs_output_v<T>,vs>::type + ts_lev(const T& v) { return {ts(v)}; } + template<int lev, class T> typename enable_if<needs_output_v<T>,vs>::type + ts_lev(const T& v) { + if (lev == 0 || !sz(v)) return {ts(v)}; + vs res; + for (const auto& t: v) { + if (sz(res)) res.bk += ","; + vs tmp = ts_lev<lev-1>(t); + res.ins(end(res),all(tmp)); + } + F0R(i,sz(res)) { + str bef = " "; if (i == 0) bef = "{"; + res[i] = bef+res[i]; + } + res.bk += "}"; + return res; + } +} + +inline namespace Output { + template<class T> void pr_sep(ostream& os, str, const T& t) { os << ts(t); } + template<class T, class... U> void pr_sep(ostream& os, str 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, str 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 setIn(str s) { freopen(s.c_str(),"r",stdin); } + void setOut(str s) { freopen(s.c_str(),"w",stdout); } + void setIO(str 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 (sz(s)) setIn(s+".in"), setOut(s+".out"); // for old USACO + } +} + +// make sure to intialize ALL GLOBAL VARS between tcs! + +/** + * Description: Big Integer + * Source: https://github.com/indy256/codelibrary/blob/master/cpp/numeric/bigint.cpp + * oops that one uses FFT instead of Karatsuba now .... + * Verification: https://oj.uz/problem/view/IOI11_parrots + */ + +// base and base_digits must be consistent +const int base = 1e9, base_digits = 9; +struct bigint { // value == 0 is represented by empty z + vi z; // digits + int sign; // sign == 1 <==> value >= 0 + bigint() : sign(1) {} // sign == -1 <==> value < 0 + bigint(ll v) { *this = v; } + bigint &operator=(ll v) { + sign = v < 0 ? -1 : 1; v *= sign; // make v positive + z.clear(); for (;v;v/=base) z.pb(v%base); + return *this; + } + bigint(const str &s) { read(s); } // add char by char + + bigint &operator+=(const bigint &other) { + //dbg("ADDING",*this,other,sign,other.sign); + if (sign == other.sign) { + for (int i = 0, carry = 0; i < sz(other.z) || carry; ++i) { + if (i == sz(z)) z.pb(0); + z[i] += carry+(i<sz(other.z)?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 < sz(other.z) || carry; ++i) { + z[i] -= carry+(i<sz(other.z)?other.z[i]:0); + carry = z[i]<0; if (carry) z[i] += base; + } + trim(); + } else { // result will change sign + *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) { // oops make sure not to multiply by ll ... + if (v < 0) sign = -sign, v = -v; + for (int i = 0, carry = 0; i < sz(z) || carry; ++i) { + if (i == sz(z)) z.pb(0); + ll cur = (ll)z[i]*v+carry; + carry = cur/base; z[i] = cur%base; + } + trim(); return *this; + } + bigint operator*(int v) const { return bigint(*this) *= v; } + friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) { + int norm = base/(b1.z.bk+1); + bigint a = a1.abs()*norm, b = b1.abs()*norm, q, r; // make last element of b big + q.z.rsz(sz(a.z)); + R0F(i,sz(a.z)) { + r *= base; r += a.z[i]; + int s1 = sz(b.z) < sz(r.z) ? r.z[sz(b.z)] : 0; + int s2 = sz(b.z)-1 < sz(r.z) ? r.z[sz(b.z)-1] : 0; + int d = ((ll)s1*base+s2)/b.z.bk; // best approximation + 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 (!sz(a.z) || sz(a.z)&1) a.z.pb(0); + int n = sz(a.z), firstDigit = ::sqrt((db)a.z[n-1]*base+a.z[n-2]); + int norm = base/(firstDigit+1); a *= norm; a *= norm; + while (!sz(a.z) || sz(a.z)&1) a.z.pb(0); + bigint r = (ll)a.z[n-1]*base+a.z[n-2]; + firstDigit = (int)::sqrt((db)a.z[n-1]*base+a.z[n-2]); + int q = firstDigit; bigint res; + R0F(j,n/2) { + for (;; --q) { + bigint r1 = (r-(res*2*base+q)*q)*base*base + + (j>0?(ll)a.z[2*j-1]*base+a.z[2*j-2]:0); + if (r1 >= 0) { r = r1; break; } + } + res *= base; res += q; // add a bit to sqrt + if (j > 0) { + int d1 = sz(res.z)+2 < sz(r.z) ? r.z[sz(res.z)+2] : 0; // always 0/1? + int d2 = sz(res.z)+1 < sz(r.z) ? r.z[sz(res.z)+1] : 0; + int d3 = sz(res.z) < sz(r.z) ? r.z[sz(res.z)] : 0; + q = ((ll) d1*base*base+(ll)d2*base+d3)/(firstDigit*2); + } + } + res.trim(); return res/norm; + } + bigint operator/(const bigint &v) const { return divmod(*this, v).f; } + bigint operator%(const bigint &v) const { return divmod(*this, v).s; } + bigint &operator/=(int v) { + if (v < 0) sign = -sign, v = -v; + for (int i = sz(z)-1, rem = 0; i >= 0; --i) { + ll cur = z[i]+rem*(ll)base; + z[i] = cur/v; rem = 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; R0F(i,sz(z)) m = (z[i]+m*(ll)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 (sz(z) != sz(v.z)) return sz(z)*sign < sz(v.z) * v.sign; + R0F(i,sz(z)) if (z[i] != v.z[i]) return z[i]*sign < v.z[i]*sign; + return 0; // equal + } + 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 (sz(z) && z.bk == 0) z.pop_back(); + if (!sz(z)) sign = 1; // don't output -0 + } + bool isZero() const { return !sz(z); } + friend bigint operator-(bigint v) { + if (sz(v.z)) v.sign = -v.sign; + return v; } + bigint abs() const { return sign == 1 ? *this : -*this; } + ll longValue() const { + ll res = 0; R0F(i,sz(z)) res = res*base+z[i]; + return res*sign; } + friend bigint gcd(const bigint &a, const bigint &b) { + return b.isZero() ? a : gcd(b, a % b); } // euclidean algo + friend bigint lcm(const bigint &a, const bigint &b) { + return a/gcd(a, b) * b; } + + void read(const str &s) { + sign = 1; z.clear(); int pos = 0; + while (pos < sz(s) && (s[pos] == '-' || s[pos] == '+')) { + if (s[pos] == '-') sign = -sign; + ++pos; } // account for sign + for (int i = sz(s)-1; i >= pos; i -= base_digits) { + int x = 0; + for (int j = max(pos, i-base_digits+1); j <= i; j++) + x = x*10+s[j]-'0'; + z.pb(x); + } + trim(); + } + friend istream &operator>>(istream &is, bigint &v) { + str s; is >> s; v.read(s); return is; } + friend ostream &operator<<(ostream &os, const bigint &v) { + if (v.sign == -1) os << '-'; + os << (!sz(v.z) ? 0 : v.z.bk); + R0F(i,sz(v.z)-1) os << setw(base_digits) << setfill('0') << v.z[i]; + return os; // pad with zeroes + } + static vi convert_base(const vi &a, int old_digits, int new_digits) { + vl p(max(old_digits, new_digits) + 1); // blocks of 10^{old} -> 10^{new} + p[0] = 1; FOR(i,1,sz(p)) p[i] = p[i-1]*10; + vi res; ll 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.pb(cur%p[new_digits]); + cur /= p[new_digits]; cur_digits -= new_digits; + } + } + res.pb(cur); while (sz(res) && res.bk == 0) res.pop_back(); + return res; + } + static vl karatMul(const vl &a, const vl &b) { // karatsuba + int n = sz(a); vl res(2*n); + if (n <= 32) { // naive multiply + F0R(i,n) F0R(j,n) res[i+j] += a[i]*b[j]; + return res; } + int k = n/2; + vl a1(begin(a),begin(a)+k), a2(k+all(a)); + vl b1(begin(b),begin(b)+k), b2(k+all(b)); + vl a1b1 = karatMul(a1, b1), a2b2 = karatMul(a2, b2); + F0R(i,k) a2[i] += a1[i], b2[i] += b1[i]; + vl r = karatMul(a2, b2); // three instead of four products + F0R(i,sz(a1b1)) r[i] -= a1b1[i]; + F0R(i,sz(a2b2)) r[i] -= a2b2[i]; + F0R(i,sz(r)) res[i+k] += r[i]; + F0R(i,sz(a1b1)) res[i] += a1b1[i]; + F0R(i,sz(a2b2)) res[i+n] += a2b2[i]; + return res; + } + bigint operator*(const bigint &v) const { + if (min(sz(z),sz(v.z)) < 150) return mul_simple(v); + bigint res; res.sign = sign*v.sign; // should work as long as # of digits isn't too large (> LLONG_MAX/10^{12}) + vi a6 = convert_base(this->z, base_digits, 6); // blocks of 10^6 instead of 10^9 + vi b6 = convert_base(v.z, base_digits, 6); + vl a(all(a6)), b(all(b6)); + while (sz(a) < sz(b)) a.pb(0); + while (sz(b) < sz(a)) b.pb(0); + while (sz(a)&(sz(a)-1)) a.pb(0), b.pb(0); // make size power of 2 + vl c = karatMul(a, b); + ll cur = 0; F0R(i,sz(c)) { // process carries + cur += c[i]; res.z.pb(cur%1000000); cur /= 1000000; } + res.z = convert_base(res.z,6,base_digits); + res.trim(); return res; + } + bigint mul_simple(const bigint &v) const { + bigint res; res.sign = sign*v.sign; + res.z.rsz(sz(z)+sz(v.z)); + F0R(i,sz(z)) if (z[i]) { + ll cur = 0; for (int j = 0; j < sz(v.z) || cur; ++j) { + cur += res.z[i+j]+(ll)z[i]*(j<sz(v.z)?v.z[j]:0); + res.z[i+j] = cur%base; cur /= base; + } + } + res.trim(); return res; + } + friend str ts(const bigint& v) { + stringstream ss; ss << v; + str s; ss >> s; return s; } +}; |