题意

让你把长度为的进制数都写到一本书里面，这个书每一页可以容纳个数字，问你写完后最后一页的数字有多少

思路

一个位的进制数的数量如下计算： 第一位不能是，所以只有种选择， 接着后面每一位都可以有种选择，所以是，那么种的方案数是

这边的指数很大，我们得用拓展欧拉定理来降幂

然后对于这个很大的情况，我们可以直接取模

我们知道等于，

也就是

那么我们可以设 ，然后 ，这样就可以得到

代码

#include <bits/stdc++.h>
using namespace std;

#define dd(x) cout << #x << " = " << x << ' '
#define de(x) cout << #x << " = " << x << '\n'

typedef long long ll;

int kpow(int a, ll b, int c) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            ret = 1ll * ret * a % c;
        }
        a = 1ll * a * a % c;
        b >>= 1;
    }
    return ret;
}

int get_phi(int x) {
    int ret = 1;
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ret = ret * (i - 1);
            x /= i;
            while(x % i == 0) {
                ret = ret * i;
                x /= i;
            }
         }
    }
    if (x != 1) ret = ret * (x - 1);
    return ret;
}

int main() {
    string b, n; cin >> b >> n;
    int c; cin >> c;
    int ns = n.size(), bs = b.size();
    auto get_mod = [&] (string s, int sz, int c) {
        int ret = 0;
        for (int i = 0; i < sz; ++i) {
            ret = (1ll * ret * 10 % c + s[i] - '0') % c;
        }
        return ret;
    };
    int bm = get_mod(b, bs, c);
    // dd(bm), de(nm);
    int left = (bm + c - 1) % c;
    int right = -1;
    if (ns < 11) {
        ll nn = stol(n);
        right = kpow(bm, nn - 1, c);
    } else {
        int phi = get_phi(c);
        int nm = get_mod(n, ns, phi);
        int e = (nm - 1) % phi + phi;
        // assert((nm - 1) % phi == (nm + phi - 1) % phi);
        right = kpow(bm, e, c);
    }
    // dd(left), de(right);
    int ans = 1ll * left * right % c;
    if (!ans) ans = c;
    cout << ans << '\n';
    return 0;
}