SHARE
TWEET

Untitled

a guest Apr 24th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace::std;
  5.  
  6.  
  7.  
  8.  
  9. void Input(int&a, int&B, int&N)
  10. {
  11.     cout << "Введите a,B,N: ";
  12.     cin >> a >> B >> N;
  13. }
  14.  
  15.  
  16. int calcK(int N)
  17. {
  18.     return (int)(sqrt(N)) + 1;
  19. }
  20.  
  21.  
  22. int binpow(int value, int exponent, int modulo)
  23. {
  24.     long res = 1;
  25.     while (exponent)
  26.     {
  27.         if (exponent & 1)
  28.         {
  29.             res *= value;
  30.             res %= modulo;
  31.         }
  32.         value *= (value % modulo);
  33.         value %= modulo;
  34.         exponent >>= 1;
  35.     }
  36.     return res % modulo;
  37. }
  38.  
  39.  
  40. int ModPow(int base, int exp, int modulus)
  41. {
  42.     base %= modulus;
  43.     int result = 1;
  44.     while (exp > 0)
  45.     {
  46.         if (exp & 1) result = (result * base) % modulus;
  47.         base = (base * base) % modulus;
  48.         exp >>= 1;
  49.     }
  50.     return result;
  51. }
  52.  
  53. map <int, int> BuildBigStepsTable(int k, int a, int N)
  54. {
  55.     map<int, int> ringspace;
  56.  
  57.     for (int i = 0; i < k; i++)
  58.         ringspace[i] = ModPow(a, (i + 1)*k, N);
  59.     return ringspace;
  60.  
  61. }
  62.  
  63.  
  64. int GetSolution(map<int, int>BigSteps, int B, int a, int N)
  65. {
  66.     int BAPowJ;
  67.     for (int i = 0; i < BigSteps.size(); i++)
  68.     {
  69.         BAPowJ = B*ModPow(a, i + 1, N);
  70.         for (auto t : BigSteps)
  71.         {
  72.             if (BAPowJ == t.second)return calcK(N)*t.first - i;
  73.         }
  74.  
  75.     }
  76.     return -1;
  77.  
  78.  
  79.  
  80.  
  81. }
  82.  
  83. bool DoMapContainValueInSecond(map<int, int> myMap, int value)
  84. {
  85.     for (auto t : myMap)
  86.     {
  87.         if (t.second == value)
  88.             return true;
  89.     }
  90.     return false;
  91. }
  92.  
  93. void PrintMap(map<int, int> mapToConsole)
  94. {
  95.     for (auto x : mapToConsole)
  96.         cout << x.first << " " << x.second << endl;
  97.  
  98. }
  99.  
  100. // a^x =B(modN)
  101. int main()
  102. {
  103.     setlocale(LC_ALL, "Russian");
  104.     int a, B, N, k;
  105.  
  106.     Input(a, B, N);
  107.     k = calcK(N);
  108.     cout << "k:" << k << endl;
  109.  
  110.     map<int, int> BigSteps = BuildBigStepsTable(k, a, N);
  111.     cout << "Big steps table:" << endl;
  112.     PrintMap(BigSteps);
  113.     cout << GetSolution(BigSteps, B, a, N) << endl;
  114.  
  115.     system("pause");
  116. }
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