题面

给定A, X, M, 求$S=\sum_{i=0}^{X-1}A^i (mod M)$
($1\le A, M \le 1e9, 1\le X \le 1e12$)

题解

很容易用浅薄的小学二年级知识想到，这是个等比数列，所以我们推个公式！$$S=\frac{A^x-1}{A-1}$$，矩阵快速幂，求个逆元！这不就完事了！这也能算是个E题？

坏了！A-1和M不一定互质，逆元不一定存在（费马小定理$a^{p-1} \equiv 1(\bmod p)$要求(a, p) = 1，即a和p互质；即使用拓展欧几里得也必须要求逆元存在），这可咋办！

实际上，我们设$a_n = \sum_{i=0}^{n-1}A^i $, 那么$a_n = A a_{n - 1} + 1$！这是一个典型的矩阵快速幂，就可以避免求不一定存在的逆元了！代码如下：

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

vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
    int n = a.size();
    vector<vector<ll>> res(n, vector<ll>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= mod;
            }
        }
    }
    return res;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
    int n = a.size();
    vector<vector<ll>> res(n, vector<ll>(n));
    for (int i = 0; i < n; i++) res[i][i] = 1;
    while (b) {
        if (b & 1) res = mat_mul(res, a, mod);
        a = mat_mul(a, a, mod);
        b >>= 1;
    }
    return res;
}

int main() {
    ll a, x, m;
    cin >> a >> x >> m;
    vector<vector<ll>> f = { {a,1},{0,1} };
    vector<vector<ll>> g = mat_pow(f, x, m);
    cout << g[0][1] << endl;
    return 0;
}