题解 | #Notepad#

【Notepad】

欧拉降幂裸题。

所有$nn$位$bb$进制的数有$b^{n}b^n$个，含前导$00$的数有$b^{n-1}b^\{n-1\}$个，总共需要记录的数有$b^n-b^{n-1}=(b-1)b^{n-1}b^n-b^\{n-1\}=(b-1)b^\{n-1\}$​个，直接对$cc$​取模。

当取模结果为$00$时，最后一页记录的数字是$cc$个，需要特判一下。

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

const int N = 1e5 + 10;

int power(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int f(int n) {	// 求n的欧拉函数
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            res = res / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) res = res / n * (n - 1);
    return res;
}

int b, n, c;
string str_b, str_n;

signed main() {
    cin >> str_b >> str_n >> c;

    for (int i = 0; i < str_b.size(); i++) b = (b * 10 + (str_b[i] - '0')) % c;

    int phi_c = f(c);
    bool k = false;
    for (int i = 0; i < str_n.size(); i++) {
        n = n * 10 + (str_n[i] - '0');
        if (n - 1 >= phi_c) n %= phi_c, k = true;
    }
    n--;
    if (k) n += phi_c;
    int res = (b - 1 + c) % c * power(b, n, c) % c;
    if (!res) res = c;
    cout << res;
    
    return 0;
}