The goal is to find $$$\sum^{X-1}_{i=0}A^{i}$$$ $$$ mod $$$ $$$m$$$ , and a simple thought is that we can calculate $$$\frac{A^{X}-1}{A-1}$$$. But when we divide $$$A^{X}-1$$$ by $$$A-1$$$ then $$$mod$$$ $$$m$$$, problem occurs: when we calculate $$$A^{X}-1$$$ , it's already $$$mod$$$ $$$m$$$ ,and there's maybe no reverse to it.
To solve this problem , I use a simple method: store $$$A^i$$$ with two numbers : $$$k$$$ and $$$r$$$ ,satisfying
When we calculate $$$A^{x}$$$,we refresh $$$k$$$ and $$$r$$$ by multiplication ,then refresh $$$k$$$ by modulo $$$m$$$ , and refresh $$$r$$$ when $$$r \ge A-1 $$$ : we do $$$k$$$ $$$+=$$$ $$$r/(A-1)$$$ and $$$r$$$ $$$=$$$ $$$r$$$ % $$$(A-1)$$$ ,like a carry.
We can prove that $$$r=1$$$ when $$$A \geq 2$$$ .But if $$$A=1$$$ , we can NOT use $$$k$$$ and $$$r$$$ to store this num for $$$A-1=0$$$ . But this case is easy to solve . The result is obviously $$$X \bmod m$$$ .
Since we get
we can get
So the answer is $$$k_{X}$$$ . Noted that this method is free to change the denominator(in this problem it's $$$A-1$$$).
Code here (GNU C11)
#include<stdio.h>
#define yes printf("Yes\n")
#define no printf("No\n")
//WA but score 500 :)
struct num{
// store number in form k*deno+r ( 0 <= r < deno)
// to solve (number^b / deno) mod Mod = ?
long long k;
long long r;
};
struct num qtimes(struct num n,long long b,long long deno,long long mod){
//Warning :deno != 0
if(b>=2){
long long tmpk = (((n.k*n.k%mod)*deno)%mod + (2*n.r*n.k) % mod + n.r*n.r/deno)%mod;
long long tmpr = n.r*n.r % deno;
if (b%2==0) return qtimes({tmpk,tmpr},b/2,deno,mod);
else{
struct num tmpn = qtimes({tmpk,tmpr},b/2,deno,mod);
long long tk2 = (((n.k*tmpn.k)%mod*deno)%mod + (n.r*tmpn.k+n.k*tmpn.r) % mod + n.r*tmpn.r/deno)%mod;
long long tr2 = n.r*tmpn.r % deno;
return {tk2,tr2};
}
}
else if(b==1) return {(n.k%mod+n.r/deno)%mod,n.r%deno};
else if(b==0) return {0,1};
}
int main(){
long long a,x,m;
scanf("%lld%lld%lld",&a,&x,&m);
if (a==1) {
printf("%lld",x%m);
return 0;
}
struct num result = qtimes({1,1},x,a-1,m);
printf("%lld",result.k+(result.r-1)/(a-1));
// result = (A^x) ,--> {ans , 1}
}