[洛谷日报第30期]浅谈乘法逆元

洛谷科技

发布时间:18-08-1715:56

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

那么今天,小义就来带你走进逆元的世界。

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

简单来说就是这样:在(mod p) 意义下( p 是素数),如果 a*a'=1 ,那么我们就说 a' 是 a 的逆元。当然啦,反过来, a 也是 a' 的逆元。

也就是说,如果

那么我们就说 a' 是 a 的逆元。

那么逆元能够为我们解决什么问题呢?

这个还是要从逆元的性质说起,我们先看下去吧~

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

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

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

1.存在唯一性

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

这是为什么呢?

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

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

由于 a≠ 0 ,所以 k 一定是0 (mod p) ,即 a'=a'' ,与假设矛盾,所以 a 只能有一个逆元。

至于逆元的存在性,读者自己思考一下吧。(就是你懒!)给个提示: p 是质数所以 a,p 一定互质。

2.完全积性函数

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

这个性质是说:

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

这点也不难证:

显然

那么

所以

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

3. a*inv[b]=a/b(mod p)

显然

两边都乘以 a 得

也就是

这个结论非常重要!

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

4.卖个关子

(不要打我)

问题三:逆元怎么求呢?

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

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

(单个)求法一:枚举法

枚举 k ,检查是否满足 a*k=1 (mod p) 。

太蠢了……

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

费马小定理:当 p 为素数时, a^{p-1}=1 (mod p) 。

那么 a*a^{p-2}=1 (mod p) 。

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

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

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

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

(批量)求法四:欧拉筛

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

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

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

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

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

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

现在我们要求 k 的逆元。

令 a*k+b=p 。

把 b 换种表达, p-a*k :

那么

在 (mod p) 意义下 p=0 ,则

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

神奇吧~

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

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

【谢谢观看】

后记

感觉好多东西都没写到啊……

还有,建议这一篇的各个式子再消化一下。毕竟,一下子来这么多数学公式确实很难接受。

如果有建议,也请留言或私信我哦~

本文发布于洛谷日报,特约作者:x義x

原文地址:https://www.luogu.org/blog/zyxxs/post-xiao-yi-jiang-tan-qian-tan-sheng-fa-ni-yuan

返回顶部