费马小定理与等比数列的求和（mod 质数）

费马小定理：任意整数a， a^p≡a (mod p)，p是质数。

定理：1.对a/b≡a*x (mod n)，则称x 为b的乘法逆元，记为b^-1。

2.当模数p为质数，且b与p互质（即b不为p的倍数）时，b的乘法逆元为b^(p-2)。

对2的简单证明：

b*b^-1≡1 （mod p）。①

由费马小定理，b^(p-1)≡1 (mod p)，b*b^-1*b^(p-1)≡1 (mod p)，即 b*b^（p-2）≡ 1 (mod p)。对比①，所以得到2的结论。

所以，对等比数列和公式 a*(q^n-1)/(q-1)，就可以用快速幂求得分母的逆元，然后乘上分子的模再取模。

对等比数列 1+a+a^2+a^3+……+a^n，结果对质数p取模，分两类情况讨论：

1. a-1与p不互质，那么上面的定理2就不能使用了。但是可以发现，a%p≡1 (mod p)。所以原式就变成了 n+1。
2. 若 a-1与p不互质，则根据等比数列公式，原式就为1*[a^(n+1)-1]%p *[(a-1)^(p-2)]%p。

这样，就在极短的时间内完成了等比数列的求和，主要的时间花费都集中在快速幂部分。

代码如下：

int qpow(int a,long long b,int mod)
{
    int ans=1;
    while(b>0)
    {
        if(b&1)ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
        b=b>>1;
    }
    return ans;
}
int main()
{
    int a,n,p;
    cin>>a>>n>>p;
    int sum;
    if((a-1)%p==0)
    {
        sum=n+1;
    }
    else
    {
        sum=qpow(a,(long long)n+1,p);
        sum=(sum-1+p)%p;
        sum=(long long)sum*qpow(a-1,p-2,p)%p;
    }
    cout<<sum;
}