一、二分+快速幂
#include<bits/stdc++.h>
#define lom long long
using namespace std;
lom quick(lom a,lom b,lom c)//quick mod
{
lom ans=1;
a%=c;
while(b)
{
if(b&1) ans=ans*a%c;
a=a*a%c;
b>>=1;
}
return ans%c;
}
lom sum(lom a,lom b,lom p)
{// get the sum of the sequence of equal ratio numbers by bisection
if(b==0) return 1;
if(a==0) return 0;
if(b&1)
return ((1+quick(a,b/2+1,p)) * sum(a,b/2,p))%p;
else
return ((1+quick(a,b/2+1,p)) * sum(a,b/2-1,p) + quick(a,b/2,p))%p;
}
int main()
{
lom n,p,q;
while(cin>>q>>n>>p)
cout<<(sum(q,n,p)-1)%p<<endl;
return 0;
}
二、通项公式+逆元+快速幂
逆元：https://blog.csdn.net/qq_41431457/article/details/89813606
a/b（mod p） == a*b^(p-2) (mod p)
（1）如果 与p互质，直接逆元快速幂（默认 a1==q）
#include<bits/stdc++.h>
#define lom long long
using namespace std;
lom quick(lom a,lom b,lom c)//快速幂取模
{
lom ans=1;
a%=c;
while(b)
{
if(b&1) ans=ans*a%c;
a=a*a%c;
b>>=1;
}
return ans%c;
}
lom divi(lom a,lom b,lom p)
{
b=quick(b,p-2,p); //b的逆元
return a*b%p;
}
int main()
{
lom n,p,q;
while(cin>>q>>n>>p)
{
lom t=q*(quick(q,n,p)-1);
cout<<divi(t,q-1,p);
}
return 0;
}
（2）如果不互质 变换模值 (A/B)%P == (A%(P*B))/B%P
