API tools faq
paste
Advertisement
Guest User

Untitled

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