Add a bigint

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; }
+};