ABC293E递归分治快速幂求同种次幂之和

求$a^0 + a^1 + a^2 + ... + a^{x-1}$，值很大，模m？

有同学会想到先求出$a^x - 1$，再除以a-1，但由于可能不存在逆元，出现各种问题，建议还是分治求。

#include <stdio.h>
#define LL long long
LL n, m, i, j, k, a, x;
LL mi(LL a, LL b){
    LL s = 1;
    while(b){
        if(b&1) s = s * a % m;
        a = a * a % m, b /= 2;
    }
    return s;
}
LL dfs(LL x){
    if(x == 0) return 1;
    if(x&1){
        LL t = dfs(x/2);
        return (t + t*mi(a, x+1>>1)) % m;
    }//偶数个，前一半和为t，后一半是前一半的倍数
    else{
        return (dfs(x-1)+mi(a, x)) % m;
    }//奇数个转偶数，x次幂单独求
}//返回0次幂、1次幂、……、x次幂之和
int main(){
    scanf("%lld%lld%lld", &a, &x, &m);
    printf("%lld\n", dfs(--x)%m);
    return 0;
}