fork download
copy 
  1. // template taken from Striver_79
  2. // Remember you were also a novice when you started
  3. // hence never be rude to anyone who wants to learn something
  4. // Never open a ranklist untill and unless you are done with solving problems, wastes 3/4 minuts
  5. // Donot treat CP as a placement thing, love it and enjoy it, you will succeed for sure.
  6. // The goal is to solve problems most efficiently not just barely
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/pb_ds/tree_policy.hpp>
  10. #include <vector>
  11. #include <map>
  12. #include <set>
  13. #include <string>
  14. #include <iostream>
  15. #include <algorithm>
  16. using namespace std;
  17. using namespace __gnu_pbds;
  18. typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  19. const int mod = 1e9 + 7;
  20. #define int long long
  21. typedef long long ll;
  22. typedef vector<ll> vi;
  23. typedef vector<vector<int>> vii;
  24. typedef vector<pair<int, int>> vpi;
  25. typedef pair<int, int> pi;
  26. void myerase(ordered_set &t, int v)
  27. {
  28.     int rank = t.order_of_key(v);                     // Number of elements that are less than v in t
  29.     ordered_set::iterator it = t.find_by_order(rank); // Iterator that points to the (rank+1)th element in t
  30.     t.erase(it);
  31. }
  32. int power(long long x, unsigned int y, int p = 1e9 + 7)
  33. {
  34.     int res = 1; // Initialize result
  35.  
  36.     x = x % p; // Update x if it is more than or
  37.                // equal to p
  38.  
  39.     if (x == 0)
  40.         return 0; // In case x is divisible by p;
  41.  
  42.     while (y > 0)
  43.     {
  44.         // If y is odd, multiply x with result
  45.         if (y & 1)
  46.             res = (res * x) % p;
  47.  
  48.         // y must be even now
  49.         y = y >> 1; // y = y/2
  50.         x = (x * x) % p;
  51.     }
  52.     return res;
  53. }
  54.  
  55. // C function for extended Euclidean Algorithm (used to
  56. // find modular inverse.
  57. int gcdExtended(int a, int b, int *x, int *y)
  58. {
  59.     // Base Case
  60.     if (a == 0)
  61.     {
  62.         *x = 0, *y = 1;
  63.         return b;
  64.     }
  65.  
  66.     int x1, y1; // To store results of recursive call
  67.     int gcd = gcdExtended(b % a, a, &x1, &y1);
  68.  
  69.     // Update x and y using results of recursive
  70.     // call
  71.     *x = y1 - (b / a) * x1;
  72.     *y = x1;
  73.  
  74.     return gcd;
  75. }
  76.  
  77. int modInverse(int b, int m)
  78. {
  79.     int x, y; // used in extended GCD algorithm
  80.     int g = gcdExtended(b, m, &x, &y);
  81.  
  82.     // Return -1 if b and m are not co-prime
  83.     if (g != 1)
  84.         return -1;
  85.  
  86.     // m is added to handle negative x
  87.     return (x % m + m) % m;
  88. }
  89.  
  90. // Function to compute a/b under modulo m
  91. int modDivide(int a, int b, int m)
  92. {
  93.     a = a % m;
  94.     int inv = modInverse(b, m);
  95.     if (inv == -1)
  96.         return -1;
  97.     else
  98.         return (inv * a) % m;
  99. }
  100. ll accurateFloor(ll a, ll b)
  101. {
  102.     ll val = a / b;
  103.     while (val * b > a)
  104.         val--;
  105.     return val;
  106. }
  107. int eulerTotient(int n)
  108. {
  109.     int val = n;
  110.     for (int i = 2; i * i <= n; i++)
  111.     {
  112.         if (n % i == 0)
  113.         {
  114.             val = val - val / i;
  115.             while (n % i == 0)
  116.             {
  117.                 n = n / i;
  118.             }
  119.         }
  120.     }
  121.     if (n > 1)
  122.     {
  123.         val = val - val / n;
  124.     }
  125.     return val;
  126. }
  127. void solve()
  128. {
  129.     // Do not get stuck on a single approach for long, think of multiple ways
  130.     ll n;
  131.     cin >> n;
  132.     ll k;
  133.     cin >> k;
  134.     if (n <= 5)
  135.     {
  136.         int v = power(2, n);
  137.         int v2 = power(2, v, k);
  138.         cout << (v2 + 1) % k << "\n";
  139.         return;
  140.     }
  141.     int val1 = eulerTotient(k);
  142.     int val = power(2, n, val1);
  143.     int ans = power(2, val + val1, k);
  144.     cout << (ans + 1) % k << "\n";
  145. }
  146. int32_t main()
  147. {
  148.     // hamare saath shree raghunath to kisi baat ki chinta nahi
  149.     ios_base::sync_with_stdio(false);
  150.     cin.tie(NULL);
  151.     int t = 1;
  152.     while (t--)
  153.     {
  154.         solve();
  155.     }
  156.     return 0;
  157. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/UhJ8uc
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!