浅谈模质数意义下的乘法逆元

来源:小义讲坛 发布时间:2018-11-09 17:55:54 作者:ex_jason 阅读量:55

求乘法逆元是一个很简单的问题,特别是你掌握了扩欧求法,线性筛法之后。但是,这个问题引申出了各种的优秀想法,它也是一个模意义下的运算非常好的例子,作为一个比较简单的内容,可以说是对初学者的一扇通往模世界的大门了。

问题一:什么是乘法逆元呢?

简单来说就是这样:在\pmod p意义下,如果a*a' \equiv 1,那么我们就说a'a的逆元。当然啦,反过来,a也是a'的逆元。

(如果a,p不互质的话a是没有逆元的)

(在p不是素数的时候情况比较复杂,所以这一篇先介绍p为素数时的情况)

问题二:逆元有什么性质?

逆元的性质可真是多了去了,比较重要的有一下几个:

(在这些性质中,一般都有一个特例:0,所以我们就不谈a=0的情况了)

1.存在唯一性

对于a来说,它只会有一个,且一定有一个逆元。

这是为什么呢?

我们先假设a有两个不相等逆元:a'a'',那么一定有:

\qquad \qquad \qquad \qquad \qquad \qquad \quad a*a'\equiv a*a''\equiv1 \pmod p

不妨设a'a''-a'=k,那么

\qquad \qquad \qquad \qquad \qquad \qquad \; a*(a''-k)\equiv a*a'' \pmod p

\qquad \qquad \qquad \qquad \qquad \qquad \! a*a''-a*k\equiv a*a'' \pmod p

\qquad \qquad \qquad \qquad \qquad \qquad \qquad a*k\equiv0 \pmod p

由于a\neq 0,所以k\equiv 0\pmod p,即a'\equiv a'',与假设矛盾,所以a只能有一个逆元。

至于逆元的存在性,读者自己思考一下吧。(就是你懒!)

2.完全积性函数

为了接下来方便,我们把a的逆元表示为inv[a]吧。

这个性质是说:

两个数的逆元的积等于这两个数积的逆元,inv[a]*inv[b]\equiv inv[a*b]

这点也不难证:

显然

\qquad \qquad \qquad \qquad \qquad \qquad a*inv[a]\equiv b*inv[b]\equiv 1 \pmod p

那么\qquad \qquad \qquad \qquad \qquad a*inv[a]*b*inv[b]\equiv1*1 \pmod p

所以\qquad \qquad \qquad \qquad \qquad (a*b)*(inv[a]*inv[b])\equiv1 \pmod p

这不就是(a*b)的逆元的定义吗!

3.a*inv[b]\equiv a/b \pmod p

显然

\qquad \qquad \qquad \qquad \qquad \qquad \qquad \; b*inv[b]\equiv 1 \pmod p

两边都乘以a

\qquad \qquad\qquad \qquad \qquad \qquad \quad \; a*b*inv[b]\equiv a \pmod p

也就是

\qquad\qquad \qquad \qquad \qquad \qquad \qquad a*inv[b]\equiv a/b \pmod p

这个结论非常重要!

有时候我们需要算出a/b mod p的值,用朴素的方法,我们只能在a上不断加p,直到它能被b整除为止。当a,b,p都很大的时候,这种方法就只能凉凉了,但如果有了逆元,我们就可以非常方便,快捷地求解。

4.卖个关子

不要打我

问题三:逆元怎么求呢?

嗯,逆元确实不错,但这玩意怎么求呢?没法求我要它干嘛啊。

那我们就来看看逆元都有什么求法吧~

(单个)求法一:枚举法

枚举k,检查是否满足a*k\equiv1 \pmod p

太蠢了……

(单个)求法二:费马小定理

费马小定理:当p为素数时,a^{p-1}\equiv1 \pmod p

那么a*a^{p-2}\equiv1 \pmod p

再看看,这是不是又是逆元的定义?快速幂求出a^{p-2}即可。

(单个)求法三:扩展欧几里得

寻找a*x\equiv1 (mod p)的解其实就相当于寻找方程a*x+p*y=1的解。

再一看:a,p一定互质,这不就是扩展欧几里得算法的标准形式吗!

(批量)求法四:欧拉筛

刚才讲的都是求单个a的逆元,但如果我们要求出1~p-1所有数的逆元呢?

还记得逆元是完全积性函数吗?所以对于每个合数a,我们把所有它的因子的逆元筛出来再相乘即可。

所以我们可以直接把所有素数筛出来,对它们求逆元(二或三),再把它的逆元乘给它的倍数就可以了。

代码如下:(这里用的是快速幂,貌似扩欧比它更快)

#include <bits/stdc++.h>
using namespace std;
const int N=25000528;
int p,n;
int vis[N],pri[N];
int inv[N];
int mi(int i,int j)  //分治快速幂
{
    if (!j) return 1;
    long long now=mi(i,j>>1);
    now=now*now%p;
    if (j&1) now=now*i%p;
    return (int)now;
}
int main()
{
    cin>>n>>p;
    vis[1]=1,inv[1]=1;
    for (int i=2;i<=p-1;i++)
    {
        if (!vis[i]) pri[++pri[0]]=i,inv[i]=mi(i,p-2);
        for (int j=1;j<=pri[0];j++)
        {
            if (i*pri[j]>=p) break;
            inv[i*pri[j]]=inv[i]*inv[pri[j]];
            if (i%pri[j]==0) break;
        }
    }
    for (int i=1;i<=n;i++)
    printf("%d\n",inv[i]);
    return 0;
}

不能过P3811……换成扩欧可能有救。

(批量)求法五:线性递推

现在我们要求k的逆元。

a*k+b=p

\qquad\qquad \qquad \qquad \qquad \qquad \qquad \; b*inv[b]\equiv1 \pmod p

b换种表达,p-a*k

\qquad\qquad \qquad \qquad \qquad \qquad \quad (p-ak)*inv[b]\equiv1 \pmod p

那么

\qquad\qquad \qquad \qquad \qquad \quad \;p*inv[b]-a*k*inv[b]\equiv1 \pmod p

\pmod p意义下p\equiv0,则

\qquad\qquad \qquad \qquad \qquad \qquad \qquad -a*k*inv[b]\equiv1 \pmod p

观察ak+b=p,我们发现:a=p div k,b=p mod k,则最终

\qquad\qquad \qquad \qquad \qquad \quad -(p/k)*inv[p mod k]*k\equiv1 \pmod p

\qquad\qquad \qquad \qquad \qquad \quad -(p/k)*inv[p mod k]\equiv inv[k] \pmod p

神奇吧~

这就得出了性质4,也是我们今天最后一个求法线性递推的原理了。

实际使用的时候记得加上p来去掉负号。代码如下:(可过P3811)

#include<bits/stdc++.h>
using namespace std;

int N,p;
int inv[25000528];

int main()
{
    cin>>N>>p;
    inv[1]=1;
    for (int i=2;i<=N;i++)
    inv[i]=(long long)(p-p/i)*inv[p%i]%p;
    for (int i=1;i<=N;i++) printf("%d\n",inv[i]);
    return 0;
}

【谢谢观看】

我要评论 登录后才能发布评论

推荐阅读

 2018-11-17 14:31:12   ex_jason

最小生成树

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

 2018-11-10 07:41:45   ex_jason

并查集

 2018-11-10 07:28:04   ex_jason

写代码的小女孩

 2018-11-09 20:18:38   ex_jason

谈谈关于初赛的那些事

 2018-11-09 20:03:06   ex_jason

dijkstra 详解

  文章归档

ex_jason的博客"    我要留言
Catfish(鲶鱼) CMS V 4.8.39