考虑到有可能 $\gcd(M,A-1) \neq 1$，不能直接等比数列求和。

$f(x) = \Sigma_{i=0}^{X-1}{A^i}$

$= A^{X-1}+A^{X-2}+\dots + A^3+A^2+A^1+A^0$

$= (((1\times A+1)\times A+1)\times A+1)\dots$

可以转为为递推式：

• $f(1) = 1$
• $f(i) = f(i-1)\times A+1$

然后矩阵快速幂加速递推即可。

矩阵加速递推

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXR = 3; // 矩阵最大行数
const int MAXC = 3; // 矩阵最大列数
int MOD;
struct Mat
{
    int r, c; // 行数列数
    int m[MAXR + 1][MAXC + 1];
    Mat() { memset(m, 0, sizeof(m)); }
};
Mat operator*(const Mat &a, const Mat &b)
{
    assert(a.c == b.r);
    Mat res;
    res.r = a.r, res.c = b.c;
    for (int i = 1; i <= a.r; i++)
        for (int k = 1; k <= a.c; k++)
        {
            int temp = a.m[i][k];
            for (int j = 1; j <= b.c; j++)
                res.m[i][j] = (res.m[i][j] + temp * b.m[k][j]) % MOD;
        }
    return res;
}
Mat quick_pow(Mat a, int b)
{
    assert(a.r == a.c);
    Mat res;
    res.r = res.c = a.r;
    for (int i = 1; i <= res.r; i++)
        res.m[i][i] = 1;
    while (b > 0)
    {
        if (b % 2)
            res = res * a;
        a = a * a;
        b = b / 2;
    }
    return res;
}
signed main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    int a, x;
    cin >> a >> x >> MOD;
    // 构造矩阵
    Mat now;
    now.r = 1, now.c = 3;
    now.m[1][1] = 1, now.m[1][2] = a + 1, now.m[1][3] = 1;
    Mat ans;
    ans.r = ans.c = 3;
    ans.m[1][1] = 0, ans.m[1][2] = 0, ans.m[1][3] = 0;
    ans.m[2][1] = 1, ans.m[2][2] = a, ans.m[2][3] = 0;
    ans.m[3][1] = 0, ans.m[3][2] = 1, ans.m[3][3] = 1;
    // 计算答案
    ans = quick_pow(ans, x - 1);
    now = now * ans;
    cout << now.m[1][1] % MOD << "\n";
    return 0;
}

/*
((1*a+1)*a+1)*a+1 ...
f(0) = 1
f(x) = f(x-1)*a+1

[A11, A12, A13] * M
= [A11*M11+A12*M21+A13*M31,
    A11*M12+A12*M22+A13*M32,
     A11*M13+A12*M23+A13*M33]

[f0, f1, 1] * M
= [f1, f2, 1]
= [f1, f1 * a + 1, 1]

M = 0 0 0
    1 a 0
    0 1 1
*/