fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. // #define mod 1000000007
  5. ll mod, m;
  6. ll f(ll a, ll n, ll mod)
  7. {
  8.         ll res = a, ans = 0;
  9.         while (n)
  10.         {
  11.                 if (n % 2)
  12.                         ans = (ans + res) % mod;
  13.                 res = (res + res) % mod;
  14.                 n /= 2;
  15.         }
  16.         return ans;
  17. }
  18. ll po(ll a, ll n)
  19. {
  20.         ll res = a, ans = 1;
  21.         while (n)
  22.         {
  23.                 if (n % 2)
  24.                         ans = f(ans, res, mod);
  25.                 res = f(res, res, mod);
  26.                 n /= 2;
  27.         }
  28.         return ans;
  29. }
  30. ll aka(ll p, ll alpha)
  31. {
  32.         if (alpha == 0)
  33.                 return 1;
  34.         if (alpha == 1)
  35.                 return (p + 1) % mod;
  36.         if (alpha % 2 == 1)
  37.                 return (f(p, aka(p, alpha - 1), mod) + 1) % mod;
  38.         if (alpha % 2 == 0)
  39.                 return (f((po(p, alpha / 2) + 1), ((aka(p, alpha / 2) - 1 + mod) % mod), mod) + 1) % mod;
  40. }
  41. int main()
  42. {
  43.         ll x, n, m;
  44.         cin >> x >> n >> m;
  45.         mod = m;
  46.         cout << aka(x, n);
  47. }
Success #stdin #stdout 0s 4784KB
comments (?)
stdin
copy 
2 6 1000
stdout
copy 
127
https://ideone.com/22qLm9
language:
C++ (gcc 8.3)
created:
3 years 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!