fork download
copy 
  1. // In the name of Allah.
  2. // We're nothing and you're everything.
  3. // Ya Ali!
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9. const int maxn = 1e2 + 14, lg = 15;
  10.  
  11. /*
  12.   ######################################################################
  13.   #######################   THE   BIG   INT   ##########################
  14. */
  15. const int base = 1000000000;
  16. const int base_digits = 9; 
  17. struct bigint {
  18. 	vector<int> a;
  19. 	int sign;
  20. 	/*<arpa>*/
  21. 	int size(){
  22. 		if(a.empty())return 0;
  23. 		int ans=(a.size()-1)*base_digits;
  24. 		int ca=a.back();
  25. 		while(ca)
  26. 			ans++,ca/=10;
  27. 		return ans;
  28. 	}
  29. 	bigint operator ^(const bigint &v){
  30. 		bigint ans=1,a=*this,b=v;
  31. 		while(!b.isZero()){
  32. 			if(b%2)
  33. 				ans*=a;
  34. 			a*=a,b/=2;
  35. 		}
  36. 		return ans;
  37. 	}
  38. 	bigint modPow(bigint base, bigint exp, const bigint &mod) {
  39. 		bigint result = 1;
  40. 		base %= mod;
  41. 		while (!exp.isZero()) {
  42. 			if (exp % 2)
  43. 				result = (result * base) % mod;
  44. 			base = (base * base) % mod;
  45. 			exp /= 2;
  46. 		}
  47. 		return result;
  48. 	}
  49. 	string to_string(){
  50. 		stringstream ss;
  51. 		ss << *this;
  52. 		string s;
  53. 		ss >> s;
  54. 		return s;
  55. 	}
  56. 	int sumof(){
  57. 		string s = to_string();
  58. 		int ans = 0;
  59. 		for(auto c : s)  ans += c - '0';
  60. 		return ans;
  61. 	}
  62. 	/*</arpa>*/
  63. 	bigint() :
  64. 		sign(1) {
  65. 	}
  66.  
  67. 	bigint(long long v) {
  68. 		*this = v;
  69. 	}
  70.  
  71. 	bigint(const string &s) {
  72. 		read(s);
  73. 	}
  74.  
  75. 	void operator=(const bigint &v) {
  76. 		sign = v.sign;
  77. 		a = v.a;
  78. 	}
  79.  
  80. 	void operator=(long long v) {
  81. 		sign = 1;
  82. 		a.clear();
  83. 		if (v < 0)
  84. 			sign = -1, v = -v;
  85. 		for (; v > 0; v = v / base)
  86. 			a.push_back(v % base);
  87. 	}
  88.  
  89. 	bigint operator+(const bigint &v) const {
  90. 		if (sign == v.sign) {
  91. 			bigint res = v;
  92.  
  93. 			for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) {
  94. 				if (i == (int) res.a.size())
  95. 					res.a.push_back(0);
  96. 				res.a[i] += carry + (i < (int) a.size() ? a[i] : 0);
  97. 				carry = res.a[i] >= base;
  98. 				if (carry)
  99. 					res.a[i] -= base;
  100. 			}
  101. 			return res;
  102. 		}
  103. 		return *this - (-v);
  104. 	}
  105.  
  106. 	bigint operator-(const bigint &v) const {
  107. 		if (sign == v.sign) {
  108. 			if (abs() >= v.abs()) {
  109. 				bigint res = *this;
  110. 				for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
  111. 					res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
  112. 					carry = res.a[i] < 0;
  113. 					if (carry)
  114. 						res.a[i] += base;
  115. 				}
  116. 				res.trim();
  117. 				return res;
  118. 			}
  119. 			return -(v - *this);
  120. 		}
  121. 		return *this + (-v);
  122. 	}
  123.  
  124. 	void operator*=(int v) {
  125. 		if (v < 0)
  126. 			sign = -sign, v = -v;
  127. 		for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  128. 			if (i == (int) a.size())
  129. 				a.push_back(0);
  130. 			long long cur = a[i] * (long long) v + carry;
  131. 			carry = (int) (cur / base);
  132. 			a[i] = (int) (cur % base);
  133. 			//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  134. 		}
  135. 		trim();
  136. 	}
  137.  
  138. 	bigint operator*(int v) const {
  139. 		bigint res = *this;
  140. 		res *= v;
  141. 		return res;
  142. 	}
  143.  
  144. 	void operator*=(long long v) {
  145. 		if (v < 0)
  146. 			sign = -sign, v = -v;
  147. 		if(v > base){
  148. 			*this = *this * (v / base) * base + *this * (v % base);
  149. 			return ;
  150. 		}
  151. 		for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) {
  152. 			if (i == (int) a.size())
  153. 				a.push_back(0);
  154. 			long long cur = a[i] * (long long) v + carry;
  155. 			carry = (int) (cur / base);
  156. 			a[i] = (int) (cur % base);
  157. 			//asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base));
  158. 		}
  159. 		trim();
  160. 	}
  161.  
  162. 	bigint operator*(long long v) const {
  163. 		bigint res = *this;
  164. 		res *= v;
  165. 		return res;
  166. 	}
  167.  
  168. 	friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  169. 		int norm = base / (b1.a.back() + 1);
  170. 		bigint a = a1.abs() * norm;
  171. 		bigint b = b1.abs() * norm;
  172. 		bigint q, r;
  173. 		q.a.resize(a.a.size());
  174.  
  175. 		for (int i = a.a.size() - 1; i >= 0; i--) {
  176. 			r *= base;
  177. 			r += a.a[i];
  178. 			int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  179. 			int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  180. 			int d = ((long long) base * s1 + s2) / b.a.back();
  181. 			r -= b * d;
  182. 			while (r < 0)
  183. 				r += b, --d;
  184. 			q.a[i] = d;
  185. 		}
  186.  
  187. 		q.sign = a1.sign * b1.sign;
  188. 		r.sign = a1.sign;
  189. 		q.trim();
  190. 		r.trim();
  191. 		return make_pair(q, r / norm);
  192. 	}
  193.  
  194. 	bigint operator/(const bigint &v) const {
  195. 		return divmod(*this, v).first;
  196. 	}
  197.  
  198. 	bigint operator%(const bigint &v) const {
  199. 		return divmod(*this, v).second;
  200. 	}
  201.  
  202. 	void operator/=(int v) {
  203. 		if (v < 0)
  204. 			sign = -sign, v = -v;
  205. 		for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  206. 			long long cur = a[i] + rem * (long long) base;
  207. 			a[i] = (int) (cur / v);
  208. 			rem = (int) (cur % v);
  209. 		}
  210. 		trim();
  211. 	}
  212.  
  213. 	bigint operator/(int v) const {
  214. 		bigint res = *this;
  215. 		res /= v;
  216. 		return res;
  217. 	}
  218.  
  219. 	int operator%(int v) const {
  220. 		if (v < 0)
  221. 			v = -v;
  222. 		int m = 0;
  223. 		for (int i = a.size() - 1; i >= 0; --i)
  224. 			m = (a[i] + m * (long long) base) % v;
  225. 		return m * sign;
  226. 	}
  227.  
  228. 	void operator+=(const bigint &v) {
  229. 		*this = *this + v;
  230. 	}
  231. 	void operator-=(const bigint &v) {
  232. 		*this = *this - v;
  233. 	}
  234. 	void operator*=(const bigint &v) {
  235. 		*this = *this * v;
  236. 	}
  237. 	void operator/=(const bigint &v) {
  238. 		*this = *this / v;
  239. 	}
  240. 	void operator%=(const bigint &v){
  241. 		*this = *this % v;
  242. 	} 
  243. 	bool operator<(const bigint &v) const {
  244. 		if (sign != v.sign)
  245. 			return sign < v.sign;
  246. 		if (a.size() != v.a.size())
  247. 			return a.size() * sign < v.a.size() * v.sign;
  248. 		for (int i = a.size() - 1; i >= 0; i--)
  249. 			if (a[i] != v.a[i])
  250. 				return a[i] * sign < v.a[i] * sign;
  251. 		return false;
  252. 	}
  253.  
  254. 	bool operator>(const bigint &v) const {
  255. 		return v < *this;
  256. 	}
  257. 	bool operator<=(const bigint &v) const {
  258. 		return !(v < *this);
  259. 	}
  260. 	bool operator>=(const bigint &v) const {
  261. 		return !(*this < v);
  262. 	}
  263. 	bool operator==(const bigint &v) const {
  264. 		return !(*this < v) && !(v < *this);
  265. 	}
  266. 	bool operator!=(const bigint &v) const {
  267. 		return *this < v || v < *this;
  268. 	}
  269.  
  270. 	void trim() {
  271. 		while (!a.empty() && !a.back())
  272. 			a.pop_back();
  273. 		if (a.empty())
  274. 			sign = 1;
  275. 	}
  276.  
  277. 	bool isZero() const {
  278. 		return a.empty() || (a.size() == 1 && !a[0]);
  279. 	}
  280.  
  281. 	bigint operator-() const {
  282. 		bigint res = *this;
  283. 		res.sign = -sign;
  284. 		return res;
  285. 	}
  286.  
  287. 	bigint abs() const {
  288. 		bigint res = *this;
  289. 		res.sign *= res.sign;
  290. 		return res;
  291. 	}
  292.  
  293. 	long long longValue() const {
  294. 		long long res = 0;
  295. 		for (int i = a.size() - 1; i >= 0; i--)
  296. 			res = res * base + a[i];
  297. 		return res * sign;
  298. 	}
  299.  
  300. 	friend bigint gcd(const bigint &a, const bigint &b) {
  301. 		return b.isZero() ? a : gcd(b, a % b);
  302. 	}
  303. 	friend bigint lcm(const bigint &a, const bigint &b) {
  304. 		return a / gcd(a, b) * b;
  305. 	}
  306.  
  307. 	void read(const string &s) {
  308. 		sign = 1;
  309. 		a.clear();
  310. 		int pos = 0;
  311. 		while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  312. 			if (s[pos] == '-')
  313. 				sign = -sign;
  314. 			++pos;
  315. 		}
  316. 		for (int i = s.size() - 1; i >= pos; i -= base_digits) {
  317. 			int x = 0;
  318. 			for (int j = max(pos, i - base_digits + 1); j <= i; j++)
  319. 				x = x * 10 + s[j] - '0';
  320. 			a.push_back(x);
  321. 		}
  322. 		trim();
  323. 	}
  324.  
  325. 	friend istream& operator>>(istream &stream, bigint &v) {
  326. 		string s;
  327. 		stream >> s;
  328. 		v.read(s);
  329. 		return stream;
  330. 	}
  331.  
  332. 	friend ostream& operator<<(ostream &stream, const bigint &v) {
  333. 		if (v.sign == -1)
  334. 			stream << '-';
  335. 		stream << (v.a.empty() ? 0 : v.a.back());
  336. 		for (int i = (int) v.a.size() - 2; i >= 0; --i)
  337. 			stream << setw(base_digits) << setfill('0') << v.a[i];
  338. 		return stream;
  339. 	}
  340.  
  341. 	static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
  342. 		vector<long long> p(max(old_digits, new_digits) + 1);
  343. 		p[0] = 1;
  344. 		for (int i = 1; i < (int) p.size(); i++)
  345. 			p[i] = p[i - 1] * 10;
  346. 		vector<int> res;
  347. 		long long cur = 0;
  348. 		int cur_digits = 0;
  349. 		for (int i = 0; i < (int) a.size(); i++) {
  350. 			cur += a[i] * p[cur_digits];
  351. 			cur_digits += old_digits;
  352. 			while (cur_digits >= new_digits) {
  353. 				res.push_back(int(cur % p[new_digits]));
  354. 				cur /= p[new_digits];
  355. 				cur_digits -= new_digits;
  356. 			}
  357. 		}
  358. 		res.push_back((int) cur);
  359. 		while (!res.empty() && !res.back())
  360. 			res.pop_back();
  361. 		return res;
  362. 	}
  363.  
  364. 	typedef vector<long long> vll;
  365.  
  366. 	static vll karatsubaMultiply(const vll &a, const vll &b) {
  367. 		int n = a.size();
  368. 		vll res(n + n);
  369. 		if (n <= 32) {
  370. 			for (int i = 0; i < n; i++)
  371. 				for (int j = 0; j < n; j++)
  372. 					res[i + j] += a[i] * b[j];
  373. 			return res;
  374. 		}
  375.  
  376. 		int k = n >> 1;
  377. 		vll a1(a.begin(), a.begin() + k);
  378. 		vll a2(a.begin() + k, a.end());
  379. 		vll b1(b.begin(), b.begin() + k);
  380. 		vll b2(b.begin() + k, b.end());
  381.  
  382. 		vll a1b1 = karatsubaMultiply(a1, b1);
  383. 		vll a2b2 = karatsubaMultiply(a2, b2);
  384.  
  385. 		for (int i = 0; i < k; i++)
  386. 			a2[i] += a1[i];
  387. 		for (int i = 0; i < k; i++)
  388. 			b2[i] += b1[i];
  389.  
  390. 		vll r = karatsubaMultiply(a2, b2);
  391. 		for (int i = 0; i < (int) a1b1.size(); i++)
  392. 			r[i] -= a1b1[i];
  393. 		for (int i = 0; i < (int) a2b2.size(); i++)
  394. 			r[i] -= a2b2[i];
  395.  
  396. 		for (int i = 0; i < (int) r.size(); i++)
  397. 			res[i + k] += r[i];
  398. 		for (int i = 0; i < (int) a1b1.size(); i++)
  399. 			res[i] += a1b1[i];
  400. 		for (int i = 0; i < (int) a2b2.size(); i++)
  401. 			res[i + n] += a2b2[i];
  402. 		return res;
  403. 	}
  404.  
  405. 	bigint operator*(const bigint &v) const {
  406. 		vector<int> a6 = convert_base(this->a, base_digits, 6);
  407. 		vector<int> b6 = convert_base(v.a, base_digits, 6);
  408. 		vll a(a6.begin(), a6.end());
  409. 		vll b(b6.begin(), b6.end());
  410. 		while (a.size() < b.size())
  411. 			a.push_back(0);
  412. 		while (b.size() < a.size())
  413. 			b.push_back(0);
  414. 		while (a.size() & (a.size() - 1))
  415. 			a.push_back(0), b.push_back(0);
  416. 		vll c = karatsubaMultiply(a, b);
  417. 		bigint res;
  418. 		res.sign = sign * v.sign;
  419. 		for (int i = 0, carry = 0; i < (int) c.size(); i++) {
  420. 			long long cur = c[i] + carry;
  421. 			res.a.push_back((int) (cur % 1000000));
  422. 			carry = (int) (cur / 1000000);
  423. 		}
  424. 		res.a = convert_base(res.a, 6, base_digits);
  425. 		res.trim();
  426. 		return res;
  427. 	}
  428. };
  429. /*
  430.   #######################   THE   BIG   INT   ##########################
  431.   ######################################################################
  432. */
  433.  
  434. int main(){
  435. 	ios::sync_with_stdio(0), cin.tie(0);
  436. 	bigint a=99999999;
  437. 	a*=1000200000003000LL;
  438. 	cout<<a<<'\n';
  439. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
100019999000099999997000
https://ideone.com/i08S0B
bigint
language:
C++14 (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!