费马小定理与等比数列的求和(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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注