API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 25th, 2019
120
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 28.36 KB | None | 0 0
raw download clone embed print report
  1. /******************************************************************************
  2.  
  3. Online C++ Compiler.
  4. Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include <time.h>
  13. #include <algorithm>
  14. #include <cmath>
  15.  
  16. using namespace std;
  17. bool chet = true;
  18. bool NEG = false;
  19. vector<int> MOD = {9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9 };
  20. vector<vector<int>> deliteli = {{2}, {3}, {5}, {7}, {1, 1}, {3, 1}, {7, 1}, {9, 1}, {3, 2}, {9, 2}, {1, 3}, {7, 3}, {1, 4}, {3, 4}, {7, 4}, {3, 5},
  21. {9, 5}, {1, 6}, {7, 6}, {1,7}, {3, 7}, {9, 7}, {3, 8}, {9, 8}, {7,9}, {1, 0, 1}, {3,0,1}, {7,0,1}, {9,0,1}, {3,1,1}, {7,2,1}, {1,3,1},
  22. {7, 3,1}, {9,3,1}, {9,4,1}, {1,5,1}, {7,5,1}, {3,6,1}, {7,6,1}, {3,7,1}, {9,7,1}, {1,8,1}, {1,9,1}, {3,9,1}, {7,9,1}, {9,9,1}, {1,1,2}, {3,2,2},
  23. {7,2,2}, {9,2,2}, {3,3,2}, {9,3,2}, {1,4,2}, {1,5,2}, {7,5,2} };
  24. vector<vector<int>> bingenses;
  25. vector<vector<int>> gener;
  26. vector<vector<int>> gen1010;
  27. vector<vector<int>> gen1010CHET;
  28. vector<vector<int>> gen1010CHET1;
  29.  
  30. vector <int> multy (vector <int> U, vector <int> V)
  31. {
  32. vector <int> W(U.size() + V.size() + 1);
  33. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  34. swap(U, V);
  35.  
  36. int m = V.size();
  37. U.push_back(0);
  38.  
  39. int t;
  40. int k = 0;
  41. for (int j = 0; j < m; j++)
  42. {
  43. for (int i = 0; i < U.size(); i++)
  44. {
  45. t = U[i] * V[j] + W[i + j] + k;
  46. W[i + j] = t % 10;
  47. k = t / 10;
  48. }
  49. }
  50.  
  51. if (W.size() > 1)
  52. {
  53. int e = W.size() - 1;
  54.  
  55. while (W[e] == 0 && W.size() > 1)
  56. {
  57. W.pop_back();
  58. e--;
  59. }
  60. }
  61. return W;
  62. }
  63.  
  64. vector <int> diff (vector <int> U, vector <int> V)
  65. {
  66. int m = max(U.size(), V.size());
  67. if (U.size() > 1)
  68. {
  69. int e = U.size() - 1;
  70.  
  71. while (U[e] == 0 && U.size() > 1)
  72. {
  73. U.pop_back();
  74. e--;
  75. }
  76. }
  77.  
  78. if (V.size() > 1)
  79. {
  80. int e = V.size() - 1;
  81.  
  82. while (V[e] == 0 && V.size() > 1)
  83. {
  84. V.pop_back();
  85. e--;
  86. }
  87. }
  88.  
  89. reverse(U.begin(), U.end());
  90. reverse(V.begin(), V.end());
  91. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  92. {
  93. swap(U, V);
  94. NEG = true;
  95. }
  96. reverse(U.begin(), U.end());
  97. reverse(V.begin(), V.end());
  98. if (V.size() < U.size())
  99. {
  100. int r = U.size() - V.size();
  101. for (int i = r; i > 0; i--)
  102. V.push_back(0);
  103. }
  104.  
  105. vector <int> W;
  106. int k = 0;
  107.  
  108. for (int j = 0; j < U.size(); j++)
  109. {
  110. W.push_back((U[j] - V[j] + k + 10) % 10);
  111. k = (U[j] - V[j] + k - 9) / 10;
  112. }
  113.  
  114. for (int i = 0; i < m; i++)
  115. W.push_back(0);
  116. NEG = false;
  117.  
  118. if (W.size() > 1)
  119. {
  120. int e = W.size() - 1;
  121.  
  122. while (W[e] == 0 && W.size() > 1)
  123. {
  124. W.pop_back();
  125. e--;
  126. }
  127. }
  128. return W;
  129. }
  130.  
  131. vector <int> diff1 (vector <int> U, vector <int> V)
  132. {
  133. int m = max(U.size(), V.size());
  134. if (U.size() > 1)
  135. {
  136. int e = U.size() - 1;
  137.  
  138. while (U[e] == 0 && U.size() > 1)
  139. {
  140. U.pop_back();
  141. e--;
  142. }
  143. }
  144.  
  145. if (V.size() > 1)
  146. {
  147. int e = V.size() - 1;
  148.  
  149. while (V[e] == 0 && V.size() > 1)
  150. {
  151. V.pop_back();
  152. e--;
  153. }
  154. }
  155.  
  156. reverse(U.begin(), U.end());
  157. reverse(V.begin(), V.end());
  158. if (V.size() > U.size() || (V.size() == U.size() && V > U))
  159. {
  160. swap(U, V);
  161. NEG = true;
  162. }
  163. reverse(U.begin(), U.end());
  164. reverse(V.begin(), V.end());
  165. if (V.size() < U.size())
  166. {
  167. int r = U.size() - V.size();
  168. for (int i = r; i > 0; i--)
  169. V.push_back(0);
  170. }
  171.  
  172. vector<int> W;
  173. int k = 0;
  174.  
  175. for (int j = 0; j < U.size(); j++)
  176. {
  177. W.push_back((U[j] - V[j] + k + 10) % 10);
  178. k = (U[j] - V[j] + k - 9) / 10;
  179. }
  180.  
  181. for (int i = 0; i < m; i++)
  182. W.push_back(0);
  183.  
  184. return W;
  185. }
  186.  
  187.  
  188. vector <int> add (vector <int> U, vector <int> V)
  189. {
  190. int m = max(U.size(), V.size());
  191.  
  192. if (U.size() > 1)
  193. {
  194. int e = U.size() - 1;
  195.  
  196. while (U[e] == 0 && U.size() > 1)
  197. {
  198. U.pop_back();
  199. e--;
  200. }
  201. }
  202.  
  203. if (V.size() > 1)
  204. {
  205. int e = V.size() - 1;
  206.  
  207. while (V[e] == 0 && V.size() > 1)
  208. {
  209. V.pop_back();
  210. e--;
  211. }
  212. }
  213.  
  214. if (V.size() > U.size())
  215. swap(U, V);
  216. vector <int> W;
  217. int k = 0;
  218.  
  219. int r = U.size() - V.size();
  220. for (int i = r; i > 0; i--)
  221. V.push_back(0);
  222.  
  223. for (int j = 0; j < U.size(); j++)
  224. {
  225. W.push_back((U[j] + V[j] + k) % 10);
  226. k = (U[j] + V[j] + k) / 10;
  227. }
  228.  
  229. for (int i = 0; i < m; i++)
  230. W.push_back(0);
  231. return W;
  232. }
  233. vector <int> add1 (vector <int> U, vector <int> V)
  234. {
  235. int m = max(U.size(), V.size());
  236.  
  237. if (U.size() > 1)
  238. {
  239. int e = U.size() - 1;
  240.  
  241. while (U[e] == 0 && U.size() > 1)
  242. {
  243. U.pop_back();
  244. e--;
  245. }
  246. }
  247.  
  248. if (V.size() > 1)
  249. {
  250. int e = V.size() - 1;
  251.  
  252. while (V[e] == 0 && V.size() > 1)
  253. {
  254. V.pop_back();
  255. e--;
  256. }
  257. }
  258.  
  259. if (V.size() > U.size())
  260. swap(U, V);
  261. vector<int> W;
  262. int k = 0;
  263.  
  264. int r = U.size() - V.size();
  265. for (int i = r; i > 0; i--)
  266. V.push_back(0);
  267.  
  268. for (int j = 0; j < U.size(); j++)
  269. {
  270. W.push_back((U[j] + V[j] + k) % 10);
  271. k = (U[j] + V[j] + k) / 10;
  272. }
  273.  
  274. if (k == 1)
  275. W.push_back(k);
  276.  
  277. return W;
  278. }
  279.  
  280. vector <int> diviz (vector <int> U, vector <int> V)
  281. {
  282. bool men = false;
  283.  
  284. if (U[0] % 2 == 1)
  285. chet = false;
  286.  
  287. if (U.size() < V.size() || (V.size() == U.size() && V[0] > U[0]))
  288. {
  289. vector<int> W;
  290. W.push_back(0);
  291. men = true;
  292. return W;
  293.  
  294. }
  295.  
  296. vector <int> W(U.size() + 1);
  297. if (!men)
  298. {
  299. int m = V.size();
  300. int cur, ost = 0;
  301.  
  302. for (int j = U.size() - 1; j >= 0; j--)
  303. {
  304. cur = 10 * ost + U[j];
  305. W[j] = cur / V[0];
  306. ost = cur % V[0];
  307. }
  308.  
  309. if (W.size() > 1)
  310. {
  311. int e = W.size() - 1;
  312. while (W[e] == 0 && W.size() > 1)
  313. {
  314. W.pop_back();
  315. e--;
  316. }
  317. }
  318. }
  319. return W;
  320. }
  321.  
  322. vector <int> diviz1 (vector <int> U, vector <int> V)
  323. {
  324. bool men = false;
  325.  
  326. if (U.size() < V.size() || (V.size() == U.size() && V[0] > U[0]))
  327. {
  328. vector<int> W;
  329. W.push_back(0);
  330. men = true;
  331. return W;
  332. }
  333.  
  334. vector <int> W(U.size() + 1);
  335. if (!men)
  336. {
  337. int m = V.size();
  338. int cur, ost = 0;
  339.  
  340. for (int j = U.size() - 1; j >= 0; j--)
  341. {
  342. cur = 10 * ost + U[j];
  343. W[j] = cur / V[0];
  344. ost = cur % V[0];
  345. }
  346.  
  347. if (W.size() > 1)
  348. {
  349. int e = W.size() - 1;
  350. while (W[e] == 0 && W.size() > 1)
  351. {
  352. W.pop_back();
  353. e--;
  354. }
  355. }
  356. }
  357. return W;
  358. }
  359.  
  360.  
  361. vector <int> divmod (vector <int> U, vector <int> V)
  362. {
  363. vector<int> MOD11, W2_2;
  364. bool zer = false;
  365.  
  366. if (U[0] == '0' && U.size() == 1)
  367. {
  368. zer = true;
  369. MOD11.push_back(0);
  370. return MOD11;
  371. }
  372.  
  373. bool men = false;
  374. reverse(V.begin(), V.end());
  375. reverse(U.begin(), U.end());
  376. if (U.size() < V.size() || (V.size() == U.size() && V > U))
  377. {
  378. men = true;
  379. reverse(U.begin(), U.end());
  380. return U;
  381. }
  382.  
  383. reverse(V.begin(), V.end());
  384. reverse(U.begin(), U.end());
  385.  
  386. vector<int> W(U.size() + 1);
  387. if (!zer && !men)
  388. {
  389. int m = V.size();
  390.  
  391. int cur, ost = 0;
  392.  
  393. vector<int> Chastnoe(U.size());
  394. if (V.size() == 1) {
  395.  
  396. for (int j = U.size() - 1; j >= 0; j--)
  397. {
  398. cur = 10 * ost + U[j];
  399. W[j] = cur / V[0];
  400. ost = cur % V[0];
  401. }
  402.  
  403. MOD11.push_back(ost);
  404. return MOD11;
  405. }
  406.  
  407. else
  408. {
  409. int ms = U.size() - V.size();
  410. int d = 10 / (V[V.size() - 1] + 1);
  411. vector<int> D;
  412. D.push_back(d);
  413. U = multy(U, D);
  414. V = multy(V, D);
  415. if (ms + V.size() > U.size() - 1)
  416. U.push_back(0);
  417. for (int j = ms; j >= 0; j--)
  418. {
  419. int qk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) / V[V.size() - 1];
  420. int rk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) % V[V.size() - 1];
  421. step1: if (qk == 10 || qk*V[V.size() - 2] > 10 * rk + U[j + V.size() - 2])
  422. {
  423. qk--;
  424. rk += V[V.size() - 1];
  425. if (rk < 10)
  426. goto step1;
  427. }
  428. vector<int> QK;
  429. QK.push_back(qk);
  430. int s = j + V.size();
  431. vector<int> chu(V.size() + 1);
  432. vector<int> raz(V.size() + 1);
  433. for (int f = s; f >= j; f--)
  434. chu[f - j] = U[f];
  435.  
  436. vector<int> chupa;
  437. for (int e = 0; e <= V.size(); e++)
  438. chupa.push_back(0);
  439. chupa.push_back(1);
  440.  
  441.  
  442. raz = diff1(chu, multy(QK, V));
  443. if (NEG)
  444. raz = diff1(chupa, raz);
  445.  
  446.  
  447. Chastnoe[j] = qk;
  448. if (NEG)
  449. {
  450. Chastnoe[j]--;
  451. raz = add(V, raz);
  452. NEG = false;
  453. }
  454.  
  455. for (int f = s; f >= j; f--)
  456. U[f] = raz[f - j];
  457.  
  458. }
  459.  
  460. if (Chastnoe.size() > 1)
  461. {
  462. int e = Chastnoe.size() - 1;
  463.  
  464. while (Chastnoe[e] == 0 && Chastnoe.size() > 1)
  465. {
  466. Chastnoe.pop_back();
  467. e--;
  468. }
  469. }
  470.  
  471.  
  472. vector <int> U2;
  473.  
  474. for (int g = V.size() - 1; g >= 0; g--)
  475. U2.push_back(U[g]);
  476. reverse(U2.begin(), U2.end());
  477. vector <int> W2 (U2.size());
  478. for (int z = U2.size() - 1; z >= 0; z--)
  479. {
  480. cur = 10 * ost + U2[z];
  481. W2[z] = cur / D[0];
  482. ost = cur % D[0];
  483. }
  484. if (W2.size() > 1)
  485. {
  486. int e = W2.size() - 1;
  487. while (W2[e] == 0 && W2.size() > 1)
  488. {
  489. W2.pop_back();
  490. e--;
  491. }
  492. }
  493. NEG = false;
  494. W2_2 = W2;
  495. }
  496. }
  497. return W2_2;
  498. }
  499.  
  500. vector <int> divch (vector <int> U, vector <int> V)
  501. {
  502. vector<int> MOD11, Chastnoe_2;
  503. bool zer = false;
  504.  
  505. if (U[0] == '0' && U.size() == 1)
  506. {
  507. zer = true;
  508. MOD11.push_back(0);
  509. return MOD11;
  510. }
  511.  
  512. bool men = false;
  513. reverse(V.begin(), V.end());
  514. reverse(U.begin(), U.end());
  515. if (U.size() < V.size() || (V.size() == U.size() && V > U))
  516. {
  517. men = true;
  518. MOD11.push_back(0);
  519. return MOD11;
  520. }
  521.  
  522. reverse(V.begin(), V.end());
  523. reverse(U.begin(), U.end());
  524.  
  525. vector <int> W(U.size() + 1);
  526. if (!zer && !men)
  527. {
  528. int m = V.size();
  529.  
  530. int cur, ost = 0;
  531.  
  532. vector<int> Chastnoe(U.size());
  533. if (V.size() == 1) {
  534.  
  535. for (int j = U.size() - 1; j >= 0; j--)
  536. {
  537. cur = 10 * ost + U[j];
  538. W[j] = cur / V[0];
  539. ost = cur % V[0];
  540. }
  541.  
  542. if (W.size() > 1) {
  543. int e = W.size() - 1;
  544. while (W[e] == 0 && W.size() > 1)
  545. {
  546. W.pop_back();
  547. e--;
  548. }
  549. }
  550. return W;
  551. }
  552.  
  553. else
  554. {
  555. int ms = U.size() - V.size();
  556. int d = 10 / (V[V.size() - 1] + 1);
  557. vector <int> D;
  558. D.push_back(d);
  559. U = multy(U, D);
  560. V = multy(V, D);
  561. if (ms + V.size() > U.size() - 1)
  562. U.push_back(0);
  563. for (int j = ms; j >= 0; j--)
  564. {
  565. int qk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) / V[V.size() - 1];
  566. int rk = (U[j + V.size()] * 10 + U[j + V.size() - 1]) % V[V.size() - 1];
  567. step1: if (qk == 10 || qk*V[V.size() - 2] > 10 * rk + U[j + V.size() - 2])
  568. {
  569. qk--;
  570. rk += V[V.size() - 1];
  571. if (rk < 10)
  572. goto step1;
  573. }
  574. vector <int> QK;
  575. QK.push_back(qk);
  576. int s = j + V.size();
  577. vector <int> chu(V.size() + 1);
  578. vector <int> raz(V.size() + 1);
  579. for (int f = s; f >= j; f--)
  580. chu[f - j] = U[f];
  581.  
  582. vector <int> chupa;
  583. for (int e = 0; e <= V.size(); e++)
  584. chupa.push_back(0);
  585. chupa.push_back(1);
  586.  
  587. raz = diff1(chu, multy(QK, V));
  588. if (NEG)
  589. raz = diff1(chupa, raz);
  590.  
  591. Chastnoe[j] = qk;
  592. if (NEG)
  593. {
  594. Chastnoe[j]--;
  595. raz = add(V, raz);
  596. NEG = false;
  597. }
  598.  
  599. for (int f = s; f >= j; f--)
  600. U[f] = raz[f - j];
  601. }
  602.  
  603. if (Chastnoe.size() > 1)
  604. {
  605. int e = Chastnoe.size() - 1;
  606.  
  607. while (Chastnoe[e] == 0 && Chastnoe.size() > 1)
  608. {
  609. Chastnoe.pop_back();
  610. e--;
  611. }
  612. }
  613. NEG = false;
  614. Chastnoe_2 = Chastnoe;
  615. }
  616. }
  617. return Chastnoe_2;
  618. }
  619.  
  620. vector <int> stepmod (vector <int> U, vector <int> V, vector <int> mod1)
  621. {
  622. vector <int> Y;
  623. Y.push_back(1);
  624. vector<int> N = V;
  625. vector <int> Z = U;
  626.  
  627. vector <int> del;
  628. del.push_back(2);
  629. while (!(N.size() == 1 && N[0] == 0))
  630. {
  631. N = diviz(N, del);
  632.  
  633. if (chet)
  634. {
  635. Z = multy(Z, Z);
  636. Z = divmod(Z, mod1);
  637. }
  638. else
  639. {
  640. Y = multy(Y, Z);
  641. Y = divmod(Y, mod1);
  642.  
  643. if (N.size() == 1 && N[0] == 0)
  644. break;
  645. Z = multy(Z, Z);
  646. Z = divmod(Z, mod1);
  647.  
  648. chet = true;
  649. }
  650. }
  651.  
  652. Y = divmod(Y, mod1);
  653.  
  654. if (Y.size() > 1)
  655. {
  656. int e = Y.size() - 1;
  657.  
  658. while (Y[e] == 0 && Y.size() > 1)
  659. {
  660. Y.pop_back();
  661. e--;
  662. }
  663. }
  664. chet = true;
  665. return Y;
  666. }
  667.  
  668. vector <int> generate(int k)
  669. {
  670. vector <int> RND;
  671. step7:
  672. int et = rand();
  673. for (int i = 0; i < k; i++)
  674. {
  675. int rnd = rand();
  676.  
  677. if (rnd < et)
  678. RND.push_back(1);
  679. else
  680. RND.push_back(0);
  681. }
  682.  
  683. for (int i = 0; i < gener.size(); i++)
  684. if (RND == gener[i])
  685. {
  686. RND.clear();
  687. goto step7;
  688. }
  689. gener.push_back(RND);
  690.  
  691. return RND;
  692. }
  693.  
  694.  
  695. vector <int> gen10 (int k)
  696. {
  697. vector<int> RND;
  698. step9:
  699. int rnd = rand() % 9 + 1;
  700. RND.push_back(rnd);
  701.  
  702. for (int i = 0; i < k - 1; i++)
  703. {
  704. int rnd2 = rand() % 10;
  705. RND.push_back(rnd2);
  706. }
  707.  
  708. for (int i = 0; i < gen1010.size(); i++)
  709. if (RND == gen1010[i])
  710. {
  711. RND.clear();
  712. goto step9;
  713. }
  714.  
  715. gen1010.push_back(RND);
  716.  
  717. return RND;
  718. }
  719.  
  720.  
  721. vector <int> gen10CHET (int k)
  722. {
  723. vector <int> RND111;
  724. step9:
  725.  
  726. for (int i = 0; i < k ; i++)
  727. {
  728. int rnd21 = rand() % 10;
  729. RND111.push_back(rnd21);
  730. }
  731.  
  732. reverse(RND111.begin(), RND111.end());
  733. if (RND111.size() > 1)
  734. {
  735. int e = RND111.size() - 1;
  736.  
  737. while (RND111[e] == 0 && RND111.size() > 1)
  738. {
  739. RND111.pop_back();
  740. e--;
  741. }
  742. }
  743.  
  744. reverse(RND111.begin(), RND111.end());
  745.  
  746. for (int i = 0; i < gen1010CHET.size(); i++)
  747. if (RND111 == gen1010CHET[i])
  748. {
  749. RND111.clear();
  750. goto step9;
  751. }
  752.  
  753. gen1010CHET.push_back(RND111);
  754.  
  755. return RND111;
  756. }
  757.  
  758. vector <int> gen10CHET1 (int k)
  759. {
  760. vector <int> RND111;
  761. step9:
  762.  
  763. for (int i = 0; i < k; i++)
  764. {
  765. int rnd21 = rand() % 10;
  766. RND111.push_back(rnd21);
  767. }
  768.  
  769. reverse(RND111.begin(), RND111.end());
  770. if (RND111.size() > 1)
  771. {
  772. int e = RND111.size() - 1;
  773.  
  774. while (RND111[e] == 0 && RND111.size() > 1)
  775. {
  776. RND111.pop_back();
  777. e--;
  778. }
  779. }
  780.  
  781. reverse(RND111.begin(), RND111.end());
  782.  
  783. for (int i = 0; i < gen1010CHET1.size(); i++)
  784. if (RND111 == gen1010CHET1[i])
  785. {
  786. RND111.clear();
  787. goto step9;
  788. }
  789.  
  790. gen1010CHET1.push_back(RND111);
  791.  
  792. return RND111;
  793. }
  794.  
  795. vector <int> perevod (vector <int> bingen)
  796. {
  797. int size = bingen.size();
  798. vector<int> genten(log2(size) + 1);
  799. vector <int> del;
  800. del.push_back(2);
  801. vector <int> stepen;
  802. for (int i = 0; i < size; i++)
  803. {
  804. int st = size - i - 1;
  805. string ST;
  806. ST = to_string(st);
  807. for (int j = ST.size() - 1; j >= 0; j--)
  808. {
  809. string step_str;
  810. step_str = ST.substr(j, 1);
  811. int step_ch = atoi(step_str.c_str());
  812. stepen.push_back(step_ch);
  813. }
  814. vector <int> bg;
  815. bg.push_back(bingen[i]);
  816. genten = add1(genten, multy(bg, stepmod(del, stepen, MOD)));
  817. bg.clear();
  818. stepen.clear();
  819. }
  820.  
  821. if (genten.size() > 1)
  822. {
  823. int e = genten.size() - 1;
  824.  
  825. while (genten[e] == 0 && genten.size() > 1)
  826. {
  827. genten.pop_back();
  828. e--;
  829. }
  830. }
  831. return genten;
  832. }
  833.  
  834. bool comvec (vector <int> &V, vector <int> &U)
  835. {
  836. if (V.size() < U.size())
  837. return true;
  838. if (V.size() > U.size())
  839. return false;
  840. if (V == U)
  841. return false;
  842.  
  843. for (int g = 0; g < V.size(); g++)
  844. {
  845. if (V[g] > U[g])
  846. return false;
  847. else {
  848. if (V[g] < U[g])
  849. return true;
  850. }
  851.  
  852. }
  853. return true;
  854. }
  855.  
  856. vector <int> binarprostgen (int &k)
  857. {
  858. vector<int> bingen;
  859. if (k == 1)
  860. {
  861. bingen.push_back(1);
  862. return bingen;
  863. }
  864.  
  865. step5:
  866. bingen.push_back(1);
  867.  
  868. for (int i = 0; i < k - 2; i++)
  869. {
  870. int rnd = rand() % 2;
  871. bingen.push_back(rnd);
  872. }
  873. bingen.push_back(1);
  874.  
  875. for (int i = 0; i < bingenses.size(); i++)
  876. if (bingen == bingenses[i])
  877. {
  878. bingen.clear();
  879. goto step5;
  880. }
  881.  
  882. bingenses.push_back(bingen);
  883.  
  884. return bingen;
  885. }
  886.  
  887.  
  888. bool isprimedel (vector <int> genten)
  889. {
  890. if (genten.size() == 1 && (genten[0] == 0 || genten[0] == 1 || genten[0] == 2))
  891. return true;
  892.  
  893. int cnt = 0;
  894.  
  895. vector <int> nul;
  896. nul.push_back(0);
  897.  
  898. for (int i = 1; i < deliteli.size(); i++)
  899. {
  900. if (divmod(genten, deliteli[i]) == nul)
  901. cnt++;
  902. }
  903.  
  904. if (cnt > 1)
  905. return false;
  906.  
  907. return true;
  908. }
  909.  
  910.  
  911. bool RabinMiller (vector <int> genten)
  912. {
  913. if (genten.size() == 1 && (genten[0] == 0 || genten[0] == 1 || genten[0] == 2))
  914. return true;
  915.  
  916. vector <int> q;
  917. vector <int> a;
  918. a.push_back(0);
  919. int count = 0;
  920. vector <int> ad;
  921. ad.push_back(1);
  922. vector <int> del;
  923. del.push_back(2);
  924. srand(time(NULL));
  925. if (genten != ad)
  926. {
  927. q = diff(genten, ad);
  928.  
  929. do { q = divch(q, del); count++; } while (q[0] % 2 == 0);
  930.  
  931. vector <int> I;
  932. I.push_back(1);
  933.  
  934. vector <int> Imax;
  935. Imax = diff(genten, ad);
  936.  
  937. vector <int> I30;
  938. I30.push_back(3);
  939. I30.push_back(0);
  940.  
  941. if (comvec(I30, Imax))
  942. Imax = I30;
  943.  
  944. for (I; comvec(I, Imax); I = add1(I, ad))
  945. {
  946. vector <int>raz = diff(genten, ad);
  947. reverse(raz.begin(), raz.end());
  948.  
  949. while (comvec(a, ad) || comvec(raz, a))
  950. a = gen10CHET1(diff(genten, ad).size());
  951.  
  952. reverse(a.begin(), a.end());
  953.  
  954. if (stepmod(a, diff(genten, ad), genten) != ad)
  955. {
  956. return false;
  957. }
  958.  
  959. a = stepmod(a, q, genten);
  960. if (a != ad)
  961. {
  962. for (int e = 0; e < count; e++)
  963. if (a != ad && a != diff(genten, ad))
  964. a = divmod(multy(a, a), genten);
  965.  
  966. if (a == ad)
  967. return false;
  968. }
  969. a.clear();
  970. }
  971. return true;
  972. }
  973. else
  974. return false;
  975. }
  976.  
  977. int main()
  978. {
  979. setlocale(LC_ALL, "Russian");
  980.  
  981. string k;
  982. cout << "Введите битность числа р = ";
  983. cin >> k;
  984.  
  985. vector <int> K, P_control;
  986.  
  987. int KK = atoi(k.c_str());
  988.  
  989. int p = 0;
  990. while (k[p] == '0' && p < k.size())
  991. p++;
  992.  
  993. if (p > 1)
  994. {
  995. cout << "Ошибка ввода. Больше одного нуля подряд вначале первого числа" << endl;
  996. system("pause");
  997. return 0;
  998. }
  999. else if (p == 1 && k.size() > 1)
  1000. {
  1001. cout << "Ошибка ввода. Ноль перед другими цифрами в первом числе с двумя знаками и более" << endl;
  1002. system("pause");
  1003. return 0;
  1004. }
  1005.  
  1006. if (KK < 4)
  1007. {
  1008. cout << "Ошибка ввода!" << endl;
  1009. system("pause");
  1010. return 0;
  1011. }
  1012. for (int i = k.size() - 1; i >= 0; i--)
  1013. K.push_back(atoi(k.substr(i, 1).c_str()));
  1014.  
  1015. vector <int> del;
  1016. vector <int> K2;
  1017. del.push_back(2);
  1018. K2 = diviz1(K, del);
  1019.  
  1020. vector <int> Q;
  1021. vector <int> step2i;
  1022. vector <int> step2i1;
  1023. vector <int> ad;
  1024. ad.push_back(1);
  1025.  
  1026. KK /= 2;
  1027. step2:
  1028.  
  1029. Q = binarprostgen(KK);
  1030. Q = perevod(Q);
  1031.  
  1032. if (!isprimedel(Q))
  1033. goto step2;
  1034. else
  1035. if (!RabinMiller(Q))
  1036. {
  1037. gen1010CHET1.clear();
  1038. goto step2;
  1039. }
  1040.  
  1041. vector <int> POROG1;
  1042. vector <int> POROG2;
  1043.  
  1044. POROG1 = stepmod(del, diff(K, ad), MOD);
  1045. POROG2 = stepmod(del, K, MOD);
  1046.  
  1047. step2i1 = divch(diff(POROG1, ad), Q);
  1048.  
  1049. step2i = divch(diff(POROG2, ad), Q);
  1050. step2i = add1(step2i, ad);
  1051.  
  1052. reverse(POROG1.begin(), POROG1.end());
  1053. reverse(POROG2.begin(), POROG2.end());
  1054.  
  1055. vector <int> S;
  1056. S.push_back(1);
  1057. vector <vector <int>> vecS;
  1058.  
  1059. vector <int> SIZE;
  1060. SIZE.push_back(vecS.size());
  1061.  
  1062. vector <int> st1;
  1063. st1 = step2i1;
  1064. reverse(st1.begin(), st1.end());
  1065. vector <int> st2 = step2i;
  1066. reverse(st2.begin(), st2.end());
  1067.  
  1068. vector <int> P;
  1069. bool go = false;
  1070.  
  1071. step69:
  1072.  
  1073. S = gen10CHET(step2i.size());
  1074.  
  1075. if ((!comvec(S, st1) && !comvec(st2, S)) && S[S.size() - 1] % 2 == 0)
  1076. {
  1077. vector<int> Snat;
  1078. Snat = S;
  1079. reverse(Snat.begin(), Snat.end());
  1080.  
  1081. P = add1(multy(Q, Snat), ad);
  1082.  
  1083. vector<int> V1, V2, V3;
  1084.  
  1085. V1 = stepmod(add1(multy(del, Q), ad), del, MOD);
  1086. reverse(V1.begin(), V1.end());
  1087.  
  1088. V2 = stepmod(del, multy(Q, Snat), P);
  1089. reverse(V2.begin(), V2.end());
  1090.  
  1091. V3 = stepmod(del, Snat, P);
  1092. reverse(V3.begin(), V3.end());
  1093.  
  1094. reverse(P.begin(), P.end());
  1095.  
  1096. if (comvec(P, V1) && (V2 == ad) && (V3 != ad) && comvec(P, POROG2) && comvec(POROG1, P))
  1097. {
  1098. P_control = P;
  1099. }
  1100. else
  1101. {
  1102. vector <int> vec = diff(diff(step2i, step2i1), diviz1(diff(step2i, step2i1), del));
  1103. bool fl;
  1104. if (SIZE.size() < vec.size())
  1105. fl = true;
  1106. if (SIZE.size() > vec.size())
  1107. fl = false;
  1108. if (SIZE == vec)
  1109. fl = false;
  1110.  
  1111. for (int g = 0; g < SIZE.size(); g++)
  1112. {
  1113. if (SIZE[g] > vec[g])
  1114. fl = false;
  1115. else
  1116. if (SIZE[g] < vec[g])
  1117. fl = true;
  1118. }
  1119. if (fl)
  1120. vecS.push_back(Snat);
  1121. SIZE = add1(SIZE, ad);
  1122. goto step69;
  1123. }
  1124. }
  1125. else goto step69;
  1126.  
  1127. vector <int> vec = diff(diff(step2i, step2i1), diviz1(diff(step2i, step2i1), del));
  1128. bool fl;
  1129. if (SIZE.size() < vec.size())
  1130. fl = true;
  1131. if (SIZE.size() > vec.size())
  1132. fl = false;
  1133. if (SIZE == vec)
  1134. fl = false;
  1135.  
  1136. for (int g = 0; g < SIZE.size(); g++)
  1137. {
  1138. if (SIZE[g] > vec[g])
  1139. fl = false;
  1140. else
  1141. if (SIZE[g] < vec[g])
  1142. fl = true;
  1143. }
  1144. if (!fl)
  1145. {
  1146. bingenses.clear();
  1147. gener.clear();
  1148.  
  1149. gen1010CHET1.clear();
  1150. gen1010CHET.clear();
  1151. gen1010.clear();
  1152.  
  1153. goto step2;
  1154. }
  1155.  
  1156. vector <int> g;
  1157. g.push_back(1);
  1158.  
  1159. for (int i = 0; i < P_control.size(); i++)
  1160. cout << P_control[i];
  1161. cout << "P" << endl;
  1162. reverse (P_control.begin(), P_control.end());
  1163. while (g == ad)
  1164. {
  1165. vector <int> a, d;
  1166. d = diff(P_control, del);
  1167.  
  1168. for (int i = 0; i < d.size(); i++)
  1169. cout << d[i];
  1170. cout << "D" << endl;
  1171. reverse(d.begin(), d.end());
  1172. while (comvec(a, del) || comvec (d, a))
  1173. {
  1174. a = gen10CHET1(P_control.size());
  1175. for (int i = 0; i < a.size(); i++)
  1176. cout << a[i];
  1177. cout << "A_g" << endl;
  1178. }
  1179. for (int i = 0; i < a.size(); i++)
  1180. cout << a[i];
  1181. cout << "A" << endl;
  1182. vector <int> d2, d3;
  1183. d2 = diff (P_control, ad);
  1184. d3 = divch(d2, Q);
  1185. g = stepmod (a, d3, P_control);
  1186. }
  1187.  
  1188. reverse(g.begin(), g.end());
  1189. for (int i = 0; i < g.size(); i++)
  1190. cout << g[i];
  1191. cout << endl;
  1192. return 0;
  1193. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!