fork(1) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. typedef vector<int> VI;
  10. typedef long long LL;
  11.  
  12. #define FOR(x, b, e) for(int x = b; x <= (e); ++x)
  13. #define FORD(x, b, e) for(int x = b; x >= (e); --x)
  14. #define REP(x, n) for(int x = 0; x < (n); ++x)
  15. #define VAR(v, n) __typeof(n) v = (n)
  16. #define ALL(c) (c).begin(), (c).end()
  17. #define SIZE(x) ((int)(x).size())
  18. #define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  19. #define PB push_back
  20. #define ST first
  21. #define ND second
  22. struct BigNum {
  23. #define REDUCE() while(len>1 && !cyf[len-1]) len--;
  24. 	static const int BASE = 1000000000, BD = 9;
  25. 	int len, al;
  26. 	LL* cyf;
  27. 	BigNum(int v = 0, int l = 2) : len(1), al(l), cyf(new LL[l]) {
  28. 		REP(x, al) cyf[x] = 0;
  29. 		if ((cyf[0] = v) >= BASE) przen(1);
  30. 	}
  31. 	BigNum(const BigNum &a) : len(a.len), al(len), cyf(new LL[al]) {
  32. 		REP(x, al) cyf[x] = a.cyf[x];
  33. 	}
  34. 	~BigNum(){ delete cyf; }
  35. 	void Res(int l) {
  36. 		if (l>al) {
  37. 			LL* n = new LL[l = max(l, 2 * al)];
  38. 			REP(x, l) n[x] = x >= al ? 0 : cyf[x];
  39. 			delete cyf;
  40. 			cyf = n;
  41. 			al = l;
  42. 		}
  43. 	}
  44. 	void przen(int p) {
  45. 		int	x = 0;
  46. 		for (; x<p || cyf[x]<0 || cyf[x] >= BASE; x++) {
  47. 			Res(x + 2);
  48. 			if (cyf[x]<0){ LL i = (-cyf[x] - 1) / BASE + 1; cyf[x] += i*BASE; cyf[x + 1] -= i; }
  49. 			else
  50. 			if (cyf[x] >= BASE){ LL i = cyf[x] / BASE; cyf[x] -= i*BASE; cyf[x + 1] += i; }
  51. 		}
  52. 		len = max(len, x + 1);
  53. 		REDUCE();
  54. 	}
  55. #define OPER1(op) bool operator op (const BigNum &a) const
  56.  
  57. 	OPER1(== ) {
  58. 		if (a.len != len) return 0;
  59. 		REP(x, len) if (cyf[x] != a.cyf[x]) return 0;
  60. 		return 1;
  61. 	}
  62. 	OPER1(<) {
  63. 		if (len != a.len) return len<a.len;
  64. 		int x = len - 1;
  65. 		while (x && a.cyf[x] == cyf[x]) x--;
  66. 		return cyf[x]<a.cyf[x];
  67. 	}
  68. 	OPER1(>) { return a<*this; }
  69. 	OPER1(<= ) { return !(a<*this); }
  70. 	OPER1(>= ) { return !(*this<a); }
  71. 	OPER1(!= ) { return !(*this == a); }
  72.  
  73. 	BigNum &operator=(int a) {
  74. 		REP(x, len) cyf[x] = 0;
  75. 		len = 1;
  76. 		if (cyf[0] = a >= BASE) przen(1);
  77. 		return *this;
  78. 	}
  79. 	void operator+=(int a){ cyf[0] += a; przen(1); }
  80. 	void operator-=(int a){ cyf[0] -= a; przen(1); }
  81. 	void operator*=(int a){ REP(x, len) cyf[x] *= a; przen(len); }
  82. 	int operator/=(int a) {
  83. 		LL w = 0;
  84. 		FORD(p, len - 1, 0){ w = w*BASE + cyf[p]; cyf[p] = w / a; w %= a; }
  85. 		REDUCE();
  86. 		return w;
  87. 	}
  88. 	int operator%(int a) {
  89. 		LL w = 0;
  90. 		FORD(p, len - 1, 0) w = (w*BASE + cyf[p]) % a;
  91. 		return w;
  92. 	}
  93. #define OPER2(op) BigNum& operator op (const BigNum &a)
  94. 	OPER2(+= ) {
  95. 		Res(a.len);
  96. 		REP(x, a.len) cyf[x] += a.cyf[x];
  97. 		przen(a.len);
  98. 		return *this;
  99. 	}
  100. 	OPER2(-= ) {
  101. 		REP(x, a.len) cyf[x] -= a.cyf[x];
  102. 		przen(a.len);
  103. 		return *this;
  104. 	}
  105. 	OPER2(*= ) {
  106. 		BigNum c(0, len + a.len);
  107. 		REP(x, a.len) {
  108. 			REP(y, len) c.cyf[y + x] += cyf[y] * a.cyf[x];
  109. 			c.przen(len + x);
  110. 		}
  111. 		*this = c;
  112. 		return *this;
  113. 	}
  114. 	OPER2(/= ) {
  115. 		int n = max(len - a.len + 1, 1);
  116. 		BigNum d(0, n), prod;
  117. 		FORD(i, n - 1, 0) {
  118. 			int l = 0, r = BASE - 1;
  119. 			while (l<r) {
  120. 				int	m = (l + r + 1) / 2;
  121. 				if (*this < prod + (a*m << i))
  122. 					r = m - 1;
  123. 				else
  124. 					l = m;
  125. 			}
  126. 			prod += a*l << i;
  127. 			d.cyf[i] = l;
  128. 			if (l) d.len = max(d.len, i + 1);
  129. 		}
  130. 		*this = d;
  131. 		return *this;
  132. 	}
  133. 	OPER2(%= ) {
  134. 		BigNum v = *this;
  135. 		v /= a;
  136. 		v *= a;
  137. 		*this -= v;
  138. 		return *this;
  139. 	}
  140. 	OPER2(= ) {
  141. 		Res(a.len);
  142. 		FORD(x, len - 1, a.len) cyf[x] = 0;
  143. 		REP(x, a.len) cyf[x] = a.cyf[x];
  144. 		len = a.len;
  145. 		return *this;
  146. 	}
  147. 	void read(const VI &v, int p) {
  148. 		*this = 0;
  149. 		FORD(x, SIZE(v), 0) {
  150. 			*this *= p;
  151. 			*this += v[x];
  152. 		}
  153. 	}
  154. 	BigNum &operator=(string a) {
  155. 		int s = a.length();
  156. 		*this = 0;
  157. 		Res(len = s / BD + 1);
  158. 		REP(x, s) cyf[(s - x - 1) / BD] = 10 * cyf[(s - x - 1) / BD] + a[x] - '0';
  159. 		REDUCE();
  160. 		return *this;
  161. 	}
  162. 	void write() const {
  163. 		printf("%d", int(cyf[len - 1]));
  164. 		FORD(x, len - 2, 0) printf("%0*d", BD, int(cyf[x]));
  165. 	}
  166. 	void write(char *buf) const {
  167. 		int p = sprintf(buf, "%d", int(cyf[len - 1]));
  168. 		FORD(x, len - 2, 0) p += sprintf(buf + p, "%0*d", BD, int(cyf[x]));
  169. 	}
  170. 	VI write(int pod) const {
  171. 		VI w;
  172. 		BigNum v;
  173. 		v = *this;
  174. 		while (v.len>1 || v.cyf[0]) w.PB(v /= pod);
  175. 		return w;
  176. 	}
  177. 	BigNum &operator>>=(int n) {
  178. 		if (n >= len) n = len;
  179. 		REP(x, len - n) cyf[x] = cyf[x + n];
  180. 		FOR(x, len - n, n) cyf[x] = 0;
  181. 		len -= n;
  182. 		if (len == 0) len = 1;
  183. 		return *this;
  184. 	}
  185. 	BigNum &operator<<=(int n) {
  186. 		if (cyf[0] == 0 && len == 1) return *this;
  187. 		Res(len + n);
  188. 		FORD(x, len - 1, 0) cyf[x + n] = cyf[x];
  189. 		REP(x, n) cyf[x] = 0;
  190. 		len += n;
  191. 		return *this;
  192. 	}
  193. 	BigNum sqrt() {
  194. 		int n = (len + 1) / 2;
  195. 		BigNum a(0, n), sq;
  196. 		FORD(i, n - 1, 0) {
  197. 			int l = 0, r = BASE - 1;
  198. 			while (l<r) {
  199. 				int m = (l + r + 1) / 2;
  200. 				if (*this < sq + (a * 2 * m << i) + (BigNum(m)*m << 2 * i))
  201. 					r = m - 1;
  202. 				else
  203. 					l = m;
  204. 			}
  205. 			sq += (a * 2 * l << i) + (BigNum(l)*l << 2 * i);
  206. 			a.cyf[i] = l; a.len = n;
  207. 		}
  208. 		return a;
  209. 	}
  210. #define OPER3(op) BigNum operator op(const BigNum &a) \
  211. 	const {BigNum w = *this;  w op ## = a;  return w; }
  212. #define OPER4(op) BigNum operator op(int a) \
  213. 	{BigNum w = *this; w op ## = a; return w; }
  214. 	OPER3(+);
  215. 	OPER3(-);
  216. 	OPER3(*);
  217. 	OPER3(/ );
  218. 	OPER3(%);
  219. 	OPER4(<< );
  220. 	OPER4(>> );
  221. };
  222. int main() {
  223. 	BigNum a, b;
  224. 	string ta, tb;
  225. 	cin >> ta >> tb;
  226. 	a = ta; b = tb;
  227. 	cout << "a = ";
  228. 	a.write();
  229. 	cout << endl << "b = ";
  230. 	b.write();
  231. 	cout << endl << "a+b = ";
  232. 	(a + b).write();
  233. 	cout << endl << "a-b = ";
  234. 	(a - b).write();
  235. 	cout << endl << "a*b = ";
  236. 	(a*b).write();
  237. 	cout << endl << "a/b = ";
  238. 	(a / b).write();
  239. 	cout << endl << "sqrt(a) = ";
  240. 	a.sqrt().write();
  241. 	return 0;
  242. }
Success #stdin #stdout 0s 3500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
a = 0
b = 0
a+b = 0
a-b = 0
a*b = 0
a/b = 999999999
sqrt(a) = 0
https://ideone.com/pH8YBD
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!