SHARE
TWEET

Untitled

Salman_CUET_18 Feb 26th, 2020 (edited) 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. int gcd(int a, int b)
  2. {
  3.     return b == 0 ? a : gcd(b, a % b);
  4. }
  5.  
  6. #define M 1000000
  7. int marked[M / 64 + 2];
  8. #define on(x) (marked[x / 64] & (1 << (( x % 64) / 2)))
  9. #define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
  10. using namespace std;
  11. vector<int>primes;
  12. void sieve(void)
  13. {
  14.     for(int i = 3; i * i <= M; i += 2)
  15.     {
  16.         if(!on(i))
  17.         {
  18.             for(int j = i * i; j <= M; j += i + i)
  19.                 mark(j);
  20.         }
  21.     }
  22.     primes.push_back(2);
  23.     for(int i = 3; i <= M; i += 2)
  24.     {
  25.         if(!on(i))
  26.             primes.push_back(i);
  27.     }
  28. }
  29. #define N 10000
  30. int ara[N];
  31. void sieve(void)
  32. {
  33.     int i, j;
  34.     for(i = 2; i < N; i++)
  35.         ara[i] = 1;
  36.     for(i = 3; i * i <= N; i+= 2)
  37.     {
  38.         if(ara[i] == 1)
  39.             for(j = i * i ; j <= N; j+=i + i)
  40.             {
  41.                 ara[j] = 0;
  42.             }
  43.     }
  44. }
  45. int is_prime(int n)
  46. {
  47.     if(n < 2)
  48.         return 0;
  49.     else if(n == 2)
  50.         return 1;
  51.     else if(n % 2 == 0)
  52.         return 0;
  53.     else
  54.         return ara[n];
  55. }
  56. int inv[SIZE];
  57. inv[1] = 1;
  58. for ( int i = 2; i <= n; i++ ) {
  59.     inv[i] = (-(m/i) * inv[m%i] ) % m;
  60.     inv[i] = inv[i] + m;
  61. }
  62. typedef long long int ll;
  63. ll Bigmod(ll n, ll p, ll m)
  64. {
  65.     if(p == 0)
  66.         return 1;
  67.     if(p % 2 == 0)
  68.     {
  69.         ll ret = Bigmod(n, p / 2, m);
  70.         return ((ret % m) * (ret % m)) % m;
  71.     }
  72.     else
  73.         return ((n % m) * (Bigmod(n, p - 1, m) % m)) % m;
  74. }
  75. typedef long long ll;
  76. ll power(ll a, ll b, ll m)
  77. {
  78.     if(b == 1)
  79.         return a % m;
  80.     if((b & 1) == 1)
  81.         return ( power(a, b-1, m) * a ) % m;
  82.     else
  83.     {
  84.         ll x = power(a, b / 2, m);
  85.         x = (x * x) % m;
  86.         return x;
  87.     }
  88. }
  89. #include<bits/stdc++.h>
  90. #define int long long
  91. #define M 1000000
  92. #define pii pair<int, int>
  93. #define x first
  94. #define y second
  95. #define on(x) (marked[x / 64] & (1 << (( x % 64) / 2)))
  96. #define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
  97. using namespace std;
  98. int marked[M / 64 + 2];
  99. void sieve(void)
  100. {
  101.     for(int i = 3; i * i <= M; i += 2)
  102.     {
  103.         if(!on(i))
  104.         {
  105.             for(int j = i * i; j <= M; j += i + i)
  106.                 mark(j);
  107.         }
  108.     }
  109. }
  110. bool IsPrime(int n)
  111. {
  112.     return n > 1 && ( n == 2 || ((n & 1) && !on(n)));
  113. }
  114. int Bigmod(int n, int p, int m)
  115. {
  116.     if(p == 0)
  117.         return 1;
  118.     if(p % 2 == 0)
  119.     {
  120.         int ret = Bigmod(n, p / 2, m);
  121.         return ((ret % m) * (ret % m)) % m;
  122.     }
  123.     else
  124.         return ((n % m) * (Bigmod(n, p - 1, m) % m)) % m;
  125. }
  126. pii extendedEuclid(int a, int b)
  127. {
  128.     if(b == 0)
  129.         return pii(1, 0);
  130.     else
  131.     {
  132.         pii d = extendedEuclid(b, a % b);
  133.         return pii(d.y, d.x - d.y * (a / b));
  134.     }
  135. }
  136. int ModInverse(int a, int m)
  137. {
  138.     pii ans = extendedEuclid(a, m);
  139.     ans.x %= m;
  140.     if(ans.x < m)
  141.         ans.x += m;
  142.     return ans.x;
  143. }
  144. main()
  145. {
  146.     sieve();
  147.     int a, m;
  148.     cin >> a >> m;
  149.     if(IsPrime(m))
  150.     {
  151.         int x = Bigmod(a, m-2, m);
  152. /// Fermat's little theorem
  153. ///  A^(M-1) ≡ 1 (mod M) (Divide both side by A)
  154. /// A^(M-2) ≡ 1/A (mod M)
  155. ///  A^(M-2) ≡ A^-1 (mod M)
  156.         cout << x << endl;
  157.     }
  158.     else
  159.         cout << ModInverse(a, m) << endl;
  160. }
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