费马小定理与等比数列的求和(mod 质数) – Zechel

费马小定理:任意整数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;
}

 

12 对 “费马小定理与等比数列的求和(mod 质数)”的想法;

  1. A excellent article, I just given this onto a colleague who was doing a analysis on this. And he ordered me lunch because I found it for him :). So let me rephrase that: Thankx for taking the time to talk about this, I feel strongly about it and enjoy learning more on this topic. If possible, as you become expertise, would you mind updating your blog with more info? It is extremely helpful for me. Robby Osbert McIntyre

  2. I am just commenting to let you understand what a nice discovery our girl experienced viewing the blog. She mastered a lot of pieces, including what it is like to possess a wonderful teaching spirit to have most people very easily fully understand specified advanced matters. You actually exceeded her expectations. Many thanks for delivering these valuable, safe, edifying not to mention fun tips about that topic to Julie. Lynett Adams Berne

  3. Thank you for any other magnificent post. Where else may anybody get that type of info in such
    an ideal approach of writing? I have a presentation next week, and I’m at the search for such information.

发表评论

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

川公网安备 51130202000337号