fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. #define si short int
  5. #define ui unsigned int
  6. #define FOR(a, b, c) for(ui b=a; b<c; b++)
  7. #define MAX(a, b) (a>b?a:b)
  8. #define max_number_of_digits 2048
  9. using namespace std;
  10. struct BigNum
  11. {
  12. 	bool sign;
  13. 	ui lenght;
  14. 	si* digits;
  15. 	BigNum ()
  16. 	{
  17. 		digits = new si[0];
  18. 		lenght=0;
  19. 		sign=0;
  20. 	}
  21. 	BigNum (si s, ui l, si* d)
  22. 	{
  23. 		digits = new si[max_number_of_digits];
  24. 		lenght = l;
  25. 		sign = s;
  26. 		memmove(digits, d, max_number_of_digits*sizeof(si));
  27. 	}
  28. 	BigNum (si s, ui l, char* d)
  29. 	{
  30. 		digits = new si[max_number_of_digits];
  31. 		lenght = l;
  32. 		sign = s;
  33. 		FOR(0, i, l)
  34. 			digits[max_number_of_digits-(l-i+1)]=(si)(d[i]-'0');
  35. 	}
  36. 	BigNum (si s, ui l, const string & d)
  37. 	{
  38. 		digits = new si[max_number_of_digits];
  39. 		lenght = l;
  40. 		sign = s;
  41. 		FOR(1, i, l+1)
  42. 			digits[max_number_of_digits-(i)]=(si)(d[l-(i)]-'0');
  43. 	}
  44. };
  45. ostream & operator << (ostream & out, const BigNum & s) 		
  46. {
  47. 	for(ui i=s.lenght; i>0; i--)
  48. 		out << s.digits[max_number_of_digits-i];
  49. 	return out;
  50. }
  51. istream & operator >> (istream & in, BigNum & s)
  52. {
  53. 	string tmp;
  54. 	in >> tmp;
  55. 	s=BigNum(0, tmp.size(), tmp);
  56. 	return in;
  57. }
  58. BigNum operator+ (BigNum & a, BigNum & b)
  59. {
  60. 	si* tmp=new si[max_number_of_digits];
  61. 	FOR(0, i, 2048) tmp[i]=0;
  62. 	for(ui i=max_number_of_digits-1; i>max_number_of_digits-(MAX(a.lenght, b.lenght)+1); i--)
  63. 	{
  64. 		tmp[i]+=a.digits[i]+b.digits[i];
  65. 		if(tmp[i]>=10)
  66. 		{
  67. 			tmp[i-1]=tmp[i]/10;
  68. 			tmp[i]%=10;
  69. 		}
  70. 	}
  71. 	return BigNum(a.sign*b.sign, MAX(a.lenght, b.lenght)+(tmp[max_number_of_digits-(MAX(a.lenght, b.lenght))]==0?1:0), tmp);
  72. }
  73. BigNum operator- (BigNum & a, BigNum & b)
  74. {
  75. 	si* tmp=new si[max_number_of_digits];
  76. 	for(ui i=max_number_of_digits-1; i>max_number_of_digits-(MAX(a.lenght, b.lenght)+1); i--)
  77. 	{
  78. 		tmp[i]+=a.digits[i]-b.digits[i];
  79. 		if(tmp[i]<0)
  80. 		{
  81. 				tmp[i-1]--;
  82. 				tmp[i]+=10;
  83. 		}
  84. 	}
  85. 	si num=0;
  86. 	for(int i=max_number_of_digits-(MAX(a.lenght, b.lenght)+1); i<max_number_of_digits; i++)
  87. 		if(tmp[i]!=0)
  88. 		{
  89. 			num=max_number_of_digits-i;
  90. 			break;
  91. 		}
  92. 	num==0?num=1:0;
  93. 	return BigNum(a.sign*b.sign, num, tmp);
  94. }
  95. bool operator < (BigNum & a, BigNum & b)
  96. {
  97. 	if(a.lenght!=b.lenght)
  98. 		return a.lenght<b.lenght;
  99. 	for(int i=max_number_of_digits-a.lenght-1; i<max_number_of_digits; i++)
  100. 		if(a.digits[i]!=b.digits[i])
  101. 			return a.digits[i]<b.digits[i];
  102. 	return false;
  103. }
  104. bool operator == (BigNum & a, BigNum & b)
  105. {
  106. 	if(a.lenght!=b.lenght)
  107. 		return false;
  108. 	for(int i=max_number_of_digits-a.lenght-1; i<max_number_of_digits; i++)
  109. 		if(a.digits[i]!=b.digits[i])
  110. 			return false;
  111. 	return true;
  112. }
  113. bool operator != (BigNum & a, BigNum & b)
  114. {
  115. 	return !(a==b);
  116. }
  117. bool operator<= (BigNum & a, BigNum & b)
  118. {
  119. 	if(a.lenght!=b.lenght)
  120. 		return a.lenght<=b.lenght;
  121. 	for(int i=max_number_of_digits-a.lenght-1; i<max_number_of_digits; i++)
  122. 		if(a.digits[i]<b.digits[i])
  123. 			return a.digits[i]<b.digits[i];
  124. 	return false;
  125. }
  126. bool operator> (BigNum & a, BigNum & b)
  127. {
  128. 	return b<a;
  129. }
  130. bool operator>= (BigNum & a, BigNum & b)
  131. {
  132. 	return b<=a;
  133. }
  134. BigNum operator* (BigNum & a, int b)
  135. {
  136. 	if (b==2)
  137. 	{
  138. 		si* tmp=new si[max_number_of_digits];
  139. 		FOR(0, i, 2048) tmp[i]=0;
  140. 		for(ui i=max_number_of_digits-1; i>max_number_of_digits-a.lenght-1; i--)
  141. 		{
  142. 			tmp[i]+=a.digits[i]*2;
  143. 			if(tmp[i]>=10)
  144. 			{
  145. 				tmp[i-1]=tmp[i]/10;
  146. 				tmp[i]%=10;
  147. 			}
  148. 		}
  149. 		return BigNum(a.sign, a.lenght+(tmp[max_number_of_digits-(a.lenght)]==0?1:0), tmp);
  150. 	}
  151. 	return BigNum();
  152. }
  153. BigNum operator/ (BigNum & a, int b)
  154. {
  155. 	si* tmp=new si[max_number_of_digits];
  156. 	for(ui i=max_number_of_digits-(a.lenght); i<max_number_of_digits; i++)
  157. 	{
  158. 		tmp[i]+=a.digits[i];
  159. 		if(tmp[i]%2==1)
  160. 				tmp[i+1]+=10;
  161. 		tmp[i]/=2;
  162. 	}
  163. 	si num;
  164. 	for(int i=max_number_of_digits-(a.lenght+1); i<max_number_of_digits; i++)
  165. 			if(tmp[i]!=0)
  166. 			{
  167. 					num=max_number_of_digits-i;
  168. 					break;
  169. 			}
  170. 	num==0?num=1:0;
  171. 	return BigNum(a.sign, num, tmp);
  172. }
  173. int operator% (BigNum & a, int b)
  174. {
  175. 	if(b==2)
  176. 	{
  177. 		return a.digits[max_number_of_digits-1]%2;
  178. 	}
  179. 	return 0;
  180. }
  181. bool operator== (BigNum & a, char b)
  182. {
  183. 	if(a.digits[max_number_of_digits-1]+'0'==b && a.lenght==1)
  184. 		return true;
  185. 	return false;
  186. }
  187. BigNum NWD(BigNum a, BigNum b)
  188. {
  189. 	si* tmp=new si[max_number_of_digits];
  190. 	tmp[max_number_of_digits-1]=1;
  191. 	BigNum zero(0, 1, tmp);
  192. 	ui dwojki=0;
  193. 	//cout << "dupa" <<endl;
  194. 	if(a<b) swap(a, b);
  195. 	while (!(b=='0') && !(b=='1'))
  196. 	{
  197.  
  198. 		if(a%2==0 && b%2==0)
  199. 		{
  200. 			dwojki++;
  201. 			a=a/2;
  202. 			b=b/2;
  203. 			cout << "(a%2==0 && b%2==0): " << a << ", " << b <<endl;
  204. 		}
  205. 		else if(a%2==1 && b%2==0)
  206. 		{
  207. 			b=b/2;
  208. 			cout << "(a%2==1 && b%2==0): " << a << ", " << b <<endl;
  209. 		}
  210. 		else if(a%2==0 && b%2==1)
  211. 		{
  212. 			a=a/2;
  213. 			cout << "(a%2==1 && b%2==0): " << a << ", " << b <<endl;
  214. 		}
  215. 		else if(a%2==1 && b%2==1)
  216. 		{
  217. 			a=a-b;
  218. 			cout << "(a%2==1 && b%2==1): " << a << ", " << b <<endl;
  219. 		}
  220. 		//if(b==zero || a==zero) break;
  221. 		if(a<b) swap(a, b);
  222. 	}
  223. 	while (dwojki--)
  224. 	{
  225. 		a=a*2;
  226. 	} 	
  227. 	return a;
  228. }
  229. int main ()
  230. {
  231.     BigNum t(0, 1, string("1"));
  232.     for (int i=0; i<13; ++i) {
  233.         t = t * 2;
  234.         cout << t << endl;
  235.     }
  236.     cout << endl << endl;
  237.  
  238.     BigNum k, l;
  239. 	while (cin >> k >> l)
  240. 	{
  241. 		cout << NWD (l, k) << endl;
  242. 	}
  243. 	return 0;
  244. }
Success #stdin #stdout 0.02s 4052KB
comments (?)
stdin
copy 
21 14
39 65 
1536 1024 
1235452 323452
5540979424919883 2018649707723796
stdout
copy 
2
4
8
6
2
4
8
6
2
4
8
6
2


(a%2==1 && b%2==0): 21, 7
(a%2==1 && b%2==1): 14, 7
(a%2==1 && b%2==0): 7, 7
(a%2==1 && b%2==1): 0, 7
7
(a%2==1 && b%2==1): 26, 39
(a%2==1 && b%2==0): 39, 13
(a%2==1 && b%2==1): 26, 13
(a%2==1 && b%2==0): 13, 13
(a%2==1 && b%2==1): 0, 13
13
(a%2==0 && b%2==0): 768, 512
(a%2==0 && b%2==0): 384, 256
(a%2==0 && b%2==0): 192, 128
(a%2==0 && b%2==0): 96, 64
(a%2==0 && b%2==0): 48, 32
(a%2==0 && b%2==0): 24, 16
(a%2==0 && b%2==0): 12, 8
(a%2==0 && b%2==0): 6, 4
(a%2==0 && b%2==0): 3, 2
(a%2==1 && b%2==0): 3, 1
6
(a%2==0 && b%2==0): 617726, 161726
(a%2==0 && b%2==0): 308863, 80863
(a%2==1 && b%2==1): 228000, 80863
(a%2==1 && b%2==0): 114000, 80863
(a%2==1 && b%2==0): 57000, 80863
(a%2==1 && b%2==0): 80863, 28500
(a%2==1 && b%2==0): 80863, 14250
(a%2==1 && b%2==0): 80863, 7125
(a%2==1 && b%2==1): 73738, 7125
(a%2==1 && b%2==0): 36869, 7125
(a%2==1 && b%2==1): 29744, 7125
(a%2==1 && b%2==0): 14872, 7125
(a%2==1 && b%2==0): 7436, 7125
(a%2==1 && b%2==0): 3718, 7125
(a%2==1 && b%2==0): 7125, 1859
(a%2==1 && b%2==1): 5266, 1859
(a%2==1 && b%2==0): 2633, 1859
(a%2==1 && b%2==1): 774, 1859
(a%2==1 && b%2==0): 1859, 387
(a%2==1 && b%2==1): 1472, 387
(a%2==1 && b%2==0): 736, 387
(a%2==1 && b%2==0): 368, 387
(a%2==1 && b%2==0): 387, 184
(a%2==1 && b%2==0): 387, 92
(a%2==1 && b%2==0): 387, 46
(a%2==1 && b%2==0): 387, 23
(a%2==1 && b%2==1): 364, 23
(a%2==1 && b%2==0): 182, 23
(a%2==1 && b%2==0): 91, 23
(a%2==1 && b%2==1): 68, 23
(a%2==1 && b%2==0): 34, 23
(a%2==1 && b%2==0): 17, 23
(a%2==1 && b%2==1): 6, 17
(a%2==1 && b%2==0): 17, 3
(a%2==1 && b%2==1): 14, 3
(a%2==1 && b%2==0): 7, 3
(a%2==1 && b%2==1): 4, 3
(a%2==1 && b%2==0): 2, 3
(a%2==1 && b%2==0): 3, 1
2
(a%2==1 && b%2==0): 5540979424919883, 1009324853861898
(a%2==1 && b%2==0): 5540979424919883, 504662426930949
(a%2==1 && b%2==1): 5036316997988934, 504662426930949
(a%2==1 && b%2==0): 2518158498994467, 504662426930949
(a%2==1 && b%2==1): 2013496072063518, 504662426930949
(a%2==1 && b%2==0): 1006748036031759, 504662426930949
(a%2==1 && b%2==1): 502085609100810, 504662426930949
(a%2==1 && b%2==0): 504662426930949, 251042804550405
(a%2==1 && b%2==1): 253619622380544, 251042804550405
(a%2==1 && b%2==0): 126809811190272, 251042804550405
(a%2==1 && b%2==0): 251042804550405, 63404905595136
(a%2==1 && b%2==0): 251042804550405, 31702452797568
(a%2==1 && b%2==0): 251042804550405, 15851226398784
(a%2==1 && b%2==0): 251042804550405, 7925613199392
(a%2==1 && b%2==0): 251042804550405, 3962806599696
(a%2==1 && b%2==0): 251042804550405, 1981403299848
(a%2==1 && b%2==0): 251042804550405, 990701649924
(a%2==1 && b%2==0): 251042804550405, 495350824962
(a%2==1 && b%2==0): 251042804550405, 247675412481
(a%2==1 && b%2==1): 250795129137924, 247675412481
(a%2==1 && b%2==0): 125397564568962, 247675412481
(a%2==1 && b%2==0): 62698782284481, 247675412481
(a%2==1 && b%2==1): 62451106872000, 247675412481
(a%2==1 && b%2==0): 31225553436000, 247675412481
(a%2==1 && b%2==0): 15612776718000, 247675412481
(a%2==1 && b%2==0): 7806388359000, 247675412481
(a%2==1 && b%2==0): 3903194179500, 247675412481
(a%2==1 && b%2==0): 1951597089750, 247675412481
(a%2==1 && b%2==0): 975798544875, 247675412481
(a%2==1 && b%2==1): 728123132394, 247675412481
(a%2==1 && b%2==0): 364061566197, 247675412481
(a%2==1 && b%2==1): 116386153716, 247675412481
(a%2==1 && b%2==0): 247675412481, 58193076858
(a%2==1 && b%2==0): 247675412481, 29096538429
(a%2==1 && b%2==1): 218578874052, 29096538429
(a%2==1 && b%2==0): 109289437026, 29096538429
(a%2==1 && b%2==0): 54644718513, 29096538429
(a%2==1 && b%2==1): 25548180084, 29096538429
(a%2==1 && b%2==0): 29096538429, 12774090042
(a%2==1 && b%2==0): 29096538429, 6387045021
(a%2==1 && b%2==1): 22709493408, 6387045021
(a%2==1 && b%2==0): 11354746704, 6387045021
(a%2==1 && b%2==0): 5677373352, 6387045021
(a%2==1 && b%2==0): 6387045021, 2838686676
(a%2==1 && b%2==0): 6387045021, 1419343338
(a%2==1 && b%2==0): 6387045021, 709671669
(a%2==1 && b%2==1): 5677373352, 709671669
(a%2==1 && b%2==0): 2838686676, 709671669
(a%2==1 && b%2==0): 1419343338, 709671669
(a%2==1 && b%2==0): 709671669, 709671669
(a%2==1 && b%2==1): 0, 709671669
709671669
https://ideone.com/hBvQty
language:
C++ (gcc 8.3)
created:
11 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!