SHARE
TWEET

Untitled

a guest Apr 25th, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
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
 
Top