fork(34) download 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. #define all(v)			((v).begin()), ((v).end())
  8. #define sz(v)			((int)((v).size()))
  9. #define clr(v, d)		memset(v, d, sizeof(v))
  10.  
  11. const int MAX = 300;
  12. typedef int big[MAX];
  13.  
  14. void big_zero (big num)			// b = 0
  15. {
  16. 	int i;
  17. 	for (i=0 ; i<MAX ; i++)
  18. 		num[i] = 0;
  19. }
  20.  
  21. void big_copy(big to, big from)	// to <-- from
  22. {
  23. 	int i;
  24. 	for(i=0;i<MAX;i++)
  25. 		to[i] = from[i];
  26. }
  27.  
  28. int big_len(big num)
  29. {
  30. 	int j;
  31. 	for (j=MAX-1; j && !num[j]; j--);
  32. 	return j;
  33. }
  34.  
  35. void big_print(big num)
  36. {
  37. 	int i;
  38. 	for (i=big_len(num); i>=0; i--)
  39. 	{
  40. 		cout<<num[i];
  41. 		if (i && !(i % 3))
  42. 			cout<<',';
  43. 	}
  44. 	cout<<"\n";
  45. }
  46.  
  47. void big_from_str(big num, string str)	// num = reverse(str)
  48. {
  49. 	int i, len = str.size()-1;
  50. 	big_zero(num);
  51.  
  52. 	for(i=len;i>-1;i--)
  53. 		num[len-i] = str[i]-'0';
  54. }//153-->153  00153-->153
  55.  
  56. string bit_to_str(big num) 
  57. {
  58. 	ostringstream oss;
  59. 	for (int i=big_len(num); i>=0; i--)
  60. 		oss<<num[i];
  61. 	return oss.str();
  62. }
  63.  
  64.  
  65. void big_from_int(big num, int x)
  66. {
  67. 	int len = 0;
  68. 	big_zero(num);
  69.  
  70. 	while(x)
  71. 	{
  72. 		num[len++] = x%10;
  73. 		x /= 10;
  74. 	}
  75. }
  76.  
  77. int big_cmp (big a, big b)		// a <=> b return 1, 0, -1
  78. {
  79. 	int i;
  80. 	for (i=MAX-1 ; i>=0 ; i--)
  81. 	{
  82. 		if (a[i] > b[i])
  83. 			return 1;
  84. 		else if (a[i] < b[i])
  85. 			return -1;
  86. 	}
  87. 	return 0;
  88. }
  89.  
  90. void big_add(big ac, int n)	//add n over a
  91. {
  92. 	int i, num, carry = n;
  93. 	for(i=0;i<MAX && carry;i++)
  94. 	{
  95. 		num  = ac[i] + carry;
  96. 		ac[i] = num%10;
  97. 		carry = num/10;
  98. 	}
  99. }
  100.  
  101. void big_add (big a, big b, big result)	// result = a + b
  102. {
  103. 	int i, carry=0;
  104. 	for (i=0 ; i<MAX ; i++)
  105. 	{
  106. 		result[i] = carry + a[i] + b[i];
  107. 		carry = result[i] / 10;
  108. 		result[i] %= 10;
  109. 	}
  110. }
  111.  
  112. char big_sub (big a, big b, big result, char sign='+')
  113. {
  114. 	if(big_cmp(a, b) < 0)
  115. 		return big_sub(b, a, result, '-');
  116.  
  117. 	big_zero(result);
  118. 	int len_a = big_len(a);
  119. 	int len_b = big_len(b);
  120.  
  121. 	int i, max = len_a > len_b ? len_a : len_b;
  122.  
  123. 	for(i=0;i<=max;i++)
  124. 		result[i] = a[i] - b[i];
  125.  
  126. 	for(i=0;i<=max;i++)
  127. 	{
  128. 		while(result[i] < 0)
  129. 		{
  130. 			result[i]   += 10;
  131. 			result[i+1] -= 1;
  132. 		}
  133. 	}
  134. 	return sign;
  135. }
  136.  
  137. void big_product(big result, int factor)
  138. {
  139.     int carry = 0;
  140.     for (int i=0; i<MAX; i++)
  141.     {
  142.         carry += result[i] * factor;
  143.         result[i] = carry % 10;
  144.         carry /= 10;
  145.     }
  146. }
  147. //Work with leading zeros
  148. void big_product(big a, big b, big result)
  149. {
  150. 	int len_a = big_len(a);
  151. 	int len_b = big_len(b);
  152.  
  153. 	if(len_a < len_b)
  154. 	{
  155. 		big_product(b, a, result);
  156. 		return;
  157. 	}
  158.  
  159. 	big_zero(result);
  160. 	int i, j;
  161.  
  162. 	int cursor = 0, pos = 0;
  163.  
  164. 	for(i=0; i<=len_b; pos = 0, cursor++, i++)
  165. 	{
  166. 		for(j=0; j<=len_a; j++, pos++)
  167. 		{
  168. 			result[pos+cursor] += b[i]*a[j];
  169.  
  170. 			if(result[pos+cursor] >= 10)
  171. 			{
  172. 				result[pos+cursor+1] += result[pos+cursor]/10;
  173. 				result[pos+cursor]   %= 10;
  174. 			}
  175. 		}
  176. 	}
  177. }
  178.  
  179. int big_divide(big ac, int div)
  180. {
  181.     int i = big_len(ac);
  182.     int reminder = 0;
  183.  
  184.     while (i >= 0)
  185.     {
  186.         reminder = reminder * 10;
  187. 		reminder = reminder + ac[i];
  188.         ac[i] = 0;
  189.  
  190.         if (div <= reminder)
  191.         {
  192.             ac[i] = reminder / div;
  193.             reminder %= div;
  194.         }
  195.         i--;
  196.     }
  197. 	return reminder;
  198. }
  199.  
  200. void big_divide(big ac, big div, big reminder)
  201. {
  202.     big cpy;
  203. 	big_zero(reminder);
  204.  
  205. 	int i = big_len(ac);
  206.  
  207.     while (i >= 0)
  208.     {
  209. 		big_product(reminder, 10);
  210.         big_add(reminder, ac[i]);
  211.         ac[i] = 0;
  212.  
  213.         while( big_cmp(reminder, div) >=0 ) //Insted of /, % is >= right or only >
  214. 		{
  215. 			big_sub(reminder, div, cpy);	//cpy = reminder-div
  216. 			big_copy(reminder, cpy);		//reminder = cpy
  217. 			ac[i]++;
  218. 		}
  219. 		i--;
  220.     }
  221.     big_print(reminder);
  222. 	big_print(ac);
  223. }
  224.  
  225. void big_mod(big a, big div, big reminder)
  226. {
  227. 	big cpy;
  228. 	big_zero(reminder);
  229.  
  230. 	int i = big_len(a);
  231.  
  232.     while (i >= 0)
  233.     {
  234. 		big_product(reminder, 10);
  235.         big_add(reminder, a[i]);
  236.  
  237.         while( big_cmp(reminder, div) >=0 ) //Insted of /, %
  238. 		{
  239. 			big_sub(reminder, div, cpy);	//cpy = reminder-div
  240. 			big_copy(reminder, cpy);		//reminder = cpy
  241. 		}
  242. 		i--;
  243.     }
  244. }
  245.  
  246. void big_gcd(big ac, big bc)	//ac: means big a will be changed
  247. {
  248. 	big t;
  249.  
  250. 	while(!(bc[0] == 0 && big_len(bc) == 0))
  251. 	{
  252. 		big_mod(ac, bc, t);	//t = a % b
  253. 		big_copy(ac, bc);		//a = b
  254. 		big_copy(bc, t);		//b = t
  255. 	}	//a now represent the gcd
  256. }
  257.  
  258.  
  259. void factorial(int n, big fact)	/* Fast untill !1200 */
  260. {
  261. 	int i, j, len;
  262.  
  263. 	big_zero(fact);
  264. 	fact[0] = 1, len = 1;
  265.  
  266. 	for(i=2; i<=n ; i++)
  267.     {
  268. 		for(j=0; j<len; j++)
  269. 			fact[j] *= i;
  270.  
  271. 		for(j=0; j<len; j++)
  272. 		{
  273. 			if(fact[j]>=10)
  274. 				fact[j+1] += fact[j]/10, fact[j] %= 10;
  275. 		}
  276.  
  277. 		while(fact[len])
  278. 			if(fact[len++]>=10)
  279. 				fact[len] += fact[len-1]/10, fact[len-1] %= 10;
  280.     }
  281. }
  282.  
  283. big remain, odd, answer, temp;	//Set them out side to save memory
  284. void big_squareRoot(string s)	//Using Pell's equation // TLE
  285. {
  286. 	long int group, count;
  287.  
  288. 	big_zero(remain);
  289. 	big_zero(odd);
  290. 	big_zero(answer);
  291.  
  292. 	if(s.size()%2 ==1)
  293. 		s = "0" + s;
  294.  
  295. 	for(int i=0;i<s.size();i+=2)
  296. 	{
  297. 		group = (s[i]-'0') * 10 + s[i+1]-'0';
  298.  
  299. 		big_copy(odd, answer);
  300. 		big_product(odd, 20);
  301. 		big_add(odd, 1);
  302.  
  303. 		big_product(remain, 100);
  304. 		big_add(remain, group);
  305.  
  306. 		count = 0;
  307. 		while( big_cmp(remain, odd) >= 0)
  308. 		{
  309. 			count++;
  310. 			big_sub(remain, odd, temp);
  311. 			big_copy(remain, temp);
  312. 			big_add(odd, 2);
  313. 		}
  314. 		big_product(answer, 10);
  315. 		big_add(answer, count);
  316. 	}
  317. 	big_print(answer);	//Contain only the int value //Give TLE
  318. }
  319.  
  320. string big_to_str(big num) {
  321. 	ostringstream oss;
  322. 	int i;
  323. 	for (i = big_len(num); i >= 0; i--) {
  324. 		oss << num[i];
  325. 	}
  326. 	return oss.str();
  327. }
  328.  
  329. string toBinay(string str) {
  330. 	big a;
  331. 	big_from_str(a, str);
  332.  
  333. 	big zero;
  334. 	big_from_int(zero, 0);
  335.  
  336. 	big two;
  337. 	big_from_int(two, 2);
  338.  
  339. 	big mod;
  340. 	string ret = "";
  341.  
  342. 	while (big_cmp(a, zero) != 0) {
  343. 		big_mod(a, two, mod);
  344. 		ret += big_to_str(mod);
  345. 		big_divide(a, 2);
  346. 	}
  347.  
  348. 	reverse(all(ret));
  349. 	return ret;
  350. }
  351.  
  352. string toDecimal(string binary) {
  353. 	big twoPow;
  354. 	big_from_int(twoPow, 1);
  355.  
  356. 	big a;
  357. 	big_zero(a);
  358.  
  359. 	big temp;
  360. 	for (int i = sz(binary) - 1; i >= 0; --i) {
  361. 		if (binary[i] == '1') {
  362. 			big_add(a, twoPow, temp);
  363. 			big_copy(a, temp);
  364. 		}
  365.  
  366. 		big_product(twoPow, 2);
  367. 	}
  368. 	return big_to_str(a);
  369. }
  370.  
  371. string fibonaccie(int n)
  372. {
  373. 	int fib[3][MAX];
  374.  
  375. 	big_from_int(fib[0], 1);
  376. 	big_from_int(fib[1], 1);
  377. 	big_from_int(fib[2], 1);
  378.  
  379. 	for(int i=2;i<n;i++)
  380. 	{
  381. 		big_add(fib[0], fib[1], fib[2]);
  382. 		big_copy(fib[0], fib[1]);
  383. 		big_copy(fib[1], fib[2]);
  384. 	}
  385. 	return bit_to_str(fib[2]);
  386. }
  387.  
  388. int main()
  389. {
  390. 	string num1, num2;
  391. 	big a, b, c;
  392.  
  393. 	while(cin>>num1>>num2)
  394. 	{
  395. 		big_from_str(a, num1);
  396. 		big_from_str(b, num2);
  397.  
  398. 		big_product(a, b, c);
  399. 		big_print(c);
  400. 	}
  401. 	return 0;
  402. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
5
6
stdout 
30
https://ideone.com/upppJ1
language:
C++ (gcc 8.3)
created:
7 years 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!