Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2019
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.24 KB | None | 0 0
  1. #include <iostream>
  2. #include<string>
  3. #include<vector>
  4. #include<algorithm>
  5.  
  6. using namespace std;
  7. bool NEG = false;
  8. vector<int> multy(vector<int>U, vector<int> V) {
  9.  
  10. vector<int> W(U.size() + V.size() + 1);
  11. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  12. swap(U, V);
  13.  
  14. int m = V.size();
  15. U.push_back(0);
  16.  
  17. int t;
  18. int i = 0, k = 0;
  19. for (int j = 0; j < m; j++)
  20. {
  21. for (int i = 0; i < U.size(); i++)
  22. {
  23. t = U[i] * V[j] + W[i + j] + k;
  24. W[i + j] = t % 10;
  25. k = t / 10;
  26. }
  27. }
  28.  
  29. if (W.size() > 1) {
  30. int e = W.size() - 1;
  31.  
  32. while (W[e] == 0 && W.size() > 1)
  33. {
  34. W.pop_back();
  35. e--;
  36. }
  37. }
  38.  
  39.  
  40.  
  41. return W;
  42.  
  43. }
  44. vector<int> diff(vector<int> U, vector<int> V) {
  45. int m = max(U.size(), V.size());
  46. if (U.size() > 1) {
  47. int e = U.size() - 1;
  48.  
  49. while (U[e] == 0 && U.size() > 1)
  50. {
  51. U.pop_back();
  52. e--;
  53. }
  54. }
  55.  
  56. if (V.size() > 1) {
  57. int e = V.size() - 1;
  58.  
  59. while (V[e] == 0 && V.size() > 1)
  60. {
  61. V.pop_back();
  62. e--;
  63. }
  64. }
  65.  
  66. reverse(U.begin(), U.end());
  67. reverse(V.begin(), V.end());
  68. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  69. {
  70. swap(U, V);
  71. NEG = true;
  72. }
  73. reverse(U.begin(), U.end());
  74. reverse(V.begin(), V.end());
  75. if (V.size() < U.size())
  76. {
  77. int r = U.size() - V.size();
  78. for (int i = r; i > 0; i--)
  79. V.push_back(0);
  80. }
  81.  
  82. vector<int> W;
  83. int k = 0;
  84.  
  85. for (int j = 0; j < U.size(); j++)
  86. {
  87. W.push_back((U[j] - V[j] + k + 10) % 10);
  88. k = (U[j] - V[j] + k - 9) / 10;
  89. }
  90.  
  91. for (int i = 0; i < m; i++)
  92. W.push_back(0);
  93.  
  94. return W;
  95. }
  96.  
  97. vector<int> add(vector<int> U, vector<int>V) {
  98. int m = max( U.size(), V.size());
  99.  
  100.  
  101. if (U.size() > 1) {
  102. int e = U.size() - 1;
  103.  
  104. while (U[e] == 0 && U.size() > 1)
  105. {
  106. U.pop_back();
  107. e--;
  108. }
  109. }
  110.  
  111. if (V.size() > 1) {
  112. int e = V.size() - 1;
  113.  
  114. while (V[e] == 0 && V.size() > 1)
  115. {
  116. V.pop_back();
  117. e--;
  118. }
  119. }
  120.  
  121. if (V.size() > U.size())
  122. swap(U, V);
  123. vector<int> W;
  124. int k = 0;
  125.  
  126. int r = U.size() - V.size();
  127. for (int i = r; i > 0; i--)
  128. V.push_back(0);
  129.  
  130. for (int j = 0; j < U.size(); j++)
  131. {
  132. W.push_back((U[j] + V[j] + k) % 10);
  133. k = (U[j] + V[j] + k) / 10;
  134. }
  135.  
  136. for (int i = 0; i < m; i++)
  137. W.push_back(0);
  138. return W;
  139. }
  140.  
  141. int main() {
  142.  
  143. setlocale(LC_ALL, "Russian");
  144. string u, v, str;
  145. cin >> u >> v;
  146.  
  147. vector<int> U;
  148. vector<int> V;
  149. int r;
  150.  
  151. bool fu = false, fv = false;
  152.  
  153. for (int i = u.size() - 1; i >= 0; i--)
  154. if (u[i] > 57 || u[i] < 48)
  155. {
  156. cout << "Ошибка ввода. В первом числе содержатся символы, отличные от цифр" << endl;
  157. fu = true;
  158. break;
  159. }
  160.  
  161. for (int i = v.size() - 1; i >= 0; i--)
  162. if (v[i] > 57 || v[i] < 48)
  163. {
  164. cout << "Ошибка ввода. Во втором числе содержатся символы, отличные от цифр" << endl;
  165. fv = true;
  166. break;
  167. }
  168.  
  169. bool fp = false, fg = false, fp1 = false, fg1 = false;
  170. int cntv = 0, cntu = 0;
  171. int p = 0;
  172. while (u[p] == '0' && p < u.size())
  173. p++;
  174.  
  175. if (p > 1)
  176. {
  177. cout << "Ошибка ввода. Больше одного нуля подряд вначале первого числа" << endl;
  178. fp = true;
  179. }
  180. else if (p == 1 && u.size() > 1)
  181. {
  182. cout << "Ошибка ввода. Ноль перед другими цифрами в первом числе с двумя знаками и более" << endl;
  183. fp1 = true;
  184.  
  185. }
  186.  
  187. int g = 0;
  188. while (v[g] == '0' && g < v.size())
  189. g++;
  190.  
  191. if (g > 1)
  192. {
  193. cout << "Ошибка ввода. Больше одного нуля подряд вначале второго числа" << endl;
  194. fg = true;
  195. }
  196. else if (g == 1 && v.size() > 1)
  197. {
  198. cout << "Ошибка ввода. Ноль перед другими цифрами во втором числе с двумя знаками и более" << endl;
  199. fp1 = true;
  200.  
  201. }
  202.  
  203. bool dz = false;
  204.  
  205. if (v[0] == '0' && v.size() == 1)
  206. {
  207. cout << "Ошибка. Деление на ноль" << endl;
  208. dz = true;
  209. }
  210.  
  211. bool zer = false;
  212.  
  213. if (u[0] == '0' && u.size() == 1 && !dz)
  214. {
  215. cout << "0" << endl << "0" << endl;
  216. zer = true;
  217. }
  218.  
  219. bool men = false;
  220.  
  221. if (u.size() < v.size() || (v.size() == u.size() && v > u))
  222. {
  223. cout << "0" << endl << u << endl;
  224. men = true;
  225. }
  226.  
  227.  
  228. vector<int> W(u.size() + 1);
  229. if (!fv && !fu && !fg && !fp && !fg1 && !fp1 && !dz && !zer && !men)
  230. {
  231.  
  232. if (v.size() > u.size() || (v.size() == u.size() && v > u))
  233. swap(u, v);
  234.  
  235. int m = v.size();
  236.  
  237.  
  238. for (int i = u.size() - 1; i >= 0; i--)
  239. {
  240. U.push_back(atoi(u.substr(i, 1).c_str()));
  241.  
  242. }
  243. for (int i = v.size() - 1; i >= 0; i--)
  244. V.push_back(atoi(v.substr(i, 1).c_str()));
  245.  
  246. int cur, ost = 0;
  247.  
  248. vector<int> Chastnoe(u.size());
  249. if (v.size() == 1) {
  250.  
  251. for (int j = U.size() - 1; j >= 0; j--)
  252. {
  253. cur = 10 * ost + U[j];
  254. W[j] = cur / V[0];
  255. ost = cur % V[0];
  256. }
  257.  
  258. if (W.size() > 1) {
  259. int e = W.size() - 1;
  260. while (W[e] == 0 && W.size() > 1)
  261. {
  262. W.pop_back();
  263. e--;
  264. }
  265. }
  266. for (int i = W.size() - 1; i >= 0; i--)
  267. cout << W[i];
  268. cout << endl;
  269.  
  270. cout << ost;
  271. cout << endl;
  272. }
  273.  
  274.  
  275. else {
  276. int ms = U.size() - V.size();
  277. int d = 10 / (V[V.size() - 1] + 1);
  278. vector<int> D;
  279. D.push_back(d);
  280. U = multy(U, D);
  281. V = multy(V, D);
  282. if (ms + V.size() > U.size() - 1)
  283. U.push_back(0);
  284. for (int j = ms; j >= 0; j--)
  285. {
  286. int qk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) / V[V.size() - 1];
  287. int rk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) % V[V.size() - 1];
  288. step1: if (qk == 10 || qk*V[V.size() - 2] > 10 * rk + U[j + V.size() - 2])
  289. {
  290. qk--;
  291. rk += V[V.size() - 1];
  292. if (rk < 10)
  293. goto step1;
  294. }
  295. vector<int> QK;
  296. QK.push_back(qk);
  297. int s = j + V.size();
  298. vector<int> chu(V.size() + 1);
  299. vector<int> raz(V.size() + 1);
  300. for (int f = s; f >= j; f--)
  301. chu[f - j] = U[f];
  302.  
  303. vector<int> chupa;
  304. for (int e = 0; e <= V.size(); e++)
  305. chupa.push_back(0);
  306. chupa.push_back(1);
  307.  
  308. raz = diff(chu, multy(QK, V));
  309. if (NEG)
  310. raz = diff(chupa, raz);
  311.  
  312. Chastnoe[j] = qk;
  313. if (NEG)
  314. {
  315. Chastnoe[j]--;
  316. raz = add(V, raz);
  317. NEG = false;
  318. }
  319.  
  320. for (int f = s; f >= j; f--)
  321. U[f] = raz[f - j];
  322. }
  323.  
  324. if (Chastnoe.size() > 1) {
  325. int e = Chastnoe.size() - 1;
  326.  
  327. while (Chastnoe[e] == 0 && Chastnoe.size() > 1)
  328. {
  329. Chastnoe.pop_back();
  330. e--;
  331. }
  332. }
  333. for (int i = Chastnoe.size() - 1; i >= 0; i--)
  334. cout << Chastnoe[i];
  335. cout << endl;
  336.  
  337. vector<int>U2;
  338.  
  339. for (int g = V.size() - 1; g >= 0; g--)
  340. U2.push_back(U[g]);
  341. reverse(U2.begin(), U2.end());
  342. vector<int> W2(U2.size());
  343. for (int z = U2.size() - 1; z >= 0; z--)
  344. {
  345. cur = 10 * ost + U2[z];
  346. W2[z] = cur / D[0];
  347. ost = cur % D[0];
  348. }
  349. if (W2.size() > 1) {
  350. int e = W2.size() - 1;
  351. while (W2[e] == 0 && W2.size() > 1)
  352. {
  353. W2.pop_back();
  354. e--;
  355. }
  356. }
  357.  
  358. for (int i = W2.size() - 1; i >= 0; i--)
  359. cout << W2[i];
  360. cout << endl;
  361. }
  362. }
  363. system("pause");
  364. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement