解法0
平方分割． \(O(x^{1/2})\) なら間に合う． \begin{align} y &:= a^{1/2}, \\ b &:= \sum_{i \in y} a^{i}, \\ c &:= \sum_{j \in y} b a^{jy} \end{align} とおく． このとき， \begin{align} c &= \sum_{i, j \in y} a^{jy + i} \\ &= \sum_{k \in y^{2}} a^{k}. \end{align} また，求める答えは \begin{align} ans &= \sum_{i \in x} a^{i} \end{align} であるから， 上の \(c\) に対して，\(x-y^{2}\) 回 \[\begin{array}[pos]{rcl} c &*=& a, \\ c &+=& 1 \end{array}\] を繰り返せば，\(ans\) が求まる． \(a\) と \(m\) は互いに素とは限らないので， \(mod\) の割り算は避けるほうが簡単． よって，\(c\) は \(ans\) を求めるときの項より 少なくなる様に定めた方が楽．
解法1
漸化式が線形なので，行列べき乗．
解法2
割り算の mod は，分母を払っておいて mod を計算して， 答えを割る．
一般に，\(a\) が \(b\) の倍数のとき， \((\frac{a}{b}) \% m = \frac{a \% (bm)}{b}\)．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll a, x, m ; cin >> a >> x >> m;
auto add = [&](ll &s, ll t) -> void {
s = (s+t)%m;
};
auto prd = [&](ll &s, ll t) -> void {
s = (s*t)%m;
};
ll y = sqrt(x);
ll d = 1;
rep(i,y){
prd(d, a);
}
ll b,c;
b = c = 0;
rep(i,y){
prd(b, a);
add(b, 1);
prd(c, d);
add(c, 1);
}
prd(c, b);
rep(i,x-y*y){
prd(c, a);
add(c, 1);
}
cout << c << endl;
return 0;
}
