fork(3) download 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define mod 1000000007
ll mod, m;
ll f(ll a, ll n, ll mod)
{
        ll res = a, ans = 0;
        while (n)
        {
                if (n % 2)
                        ans = (ans + res) % mod;
                res = (res + res) % mod;
                n /= 2;
        }
        return ans;
}
ll po(ll a, ll n)
{
        ll res = a, ans = 1;
        while (n)
        {
                if (n % 2)
                        ans = f(ans, res, mod);
                res = f(res, res, mod);
                n /= 2;
        }
        return ans;
}
ll aka(ll p, ll alpha)
{
        if (alpha == 0)
                return 1;
        if (alpha == 1)
                return (p + 1) % mod;
        if (alpha % 2 == 1)
                return (f(p, aka(p, alpha - 1), mod) + 1) % mod;
        if (alpha % 2 == 0)
                return (f((po(p, alpha / 2) + 1), ((aka(p, alpha / 2) - 1 + mod) % mod), mod) + 1) % mod;
}
int main()
{
        ll x, n, m;
        cin >> x >> n >> m;
        mod = m;
        cout << aka(x, n);
}
Success #stdin #stdout 0s 4784KB
comments (?)
stdin 
2 6 1000
stdout 
127
https://ideone.com/22qLm9
language:
C++ (gcc 8.3)
created:
4 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!