题目链接

题目链接

sloution

补充一点点，为什么奇数不能用最后一个公式呢？因为提出A的时候，结果是f(p/2)*xxxx这个需要提出一个式子，所以奇数的时候不能二分，需要用第二个式子来把他再转化成偶数。

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
ll a, x, m;
ll f[N];

ll qmi(ll n, ll k, ll p)
{
    ll res = 1 % p;
    while (k) {
        if (k & 1)
            res = res * n % p;
        n = n * n % p;
        k >>= 1;
    }
    return res;
}

ll sum(ll p)
{
    if (p == 0)
        return 1 % m;
    if (p % 2) {
        return (sum(p / 2) % m * (qmi(a, p / 2 + 1, m) + 1) % m) % m;
    } else {
        return (a * sum(p - 1) % m + 1) % m;
    }
}

void solve()
{
    cin >> a >> x >> m;
    ll ans = sum(x - 1);
    cout << ans << endl;
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}