乘法逆元3种方法总结[最全]

42 阅读 0 评论 28 点赞

我是靠谱客的博主爱撒娇钢笔，最近开发中收集的这篇文章主要介绍乘法逆元3种方法总结[最全]，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

建议大家可以先去看看这篇博文
（https://www.cnblogs.com/dupengcheng/p/5487362.html）
乘法逆元：ax≡1 (mod p) 这个等式用中文描述就是 a乘一个数x并模p等于1，即 a%p*x%p=res【并非指res等于1】,而是res%p=1;其中的x为满足范围还要对p求模

需知道的是：
若ax≡1 mod f, 则称a关于1模f的乘法逆元为x。也可表示为ax≡1(mod f)。
当a与f互素时，a关于模f的乘法逆元有解。如果不互素，则无解。如果f为素数，则从1到f-1的任意数都与f互素，即在1到f-1之间都恰好有一个关于模f的乘法逆元。【百度百科-乘法逆元】

什么是逆元，为什么要求逆元？

计蒜客某题所表述：
在这里插入图片描述
那么了解基本知识后，我们来求逆元：
求逆元分为两类：
1.a p 不互质时逆元无解
可用公式实现相同功能：

证明：

推荐题目：蓝桥杯小数第n位

2.a p 互质时：
逆元的求法主要有三种（按快慢排序）：
第一：线性打表递推法（递推公式inv[i]=(p-p/i) * inv[p%i]%p）。
第二：扩展欧几里得算法。（详解)
第三：费马小定理（快速幂qpow(a,p-2,p)）。-（最容易理解）

下面我们把每种求法的模板呈上:

例题引入：乘法逆元

Description

这是一道模板题。
给定正整数 n 与 p ，求 1∼n 中的所有数在模 p 意义下的乘法逆元。

Input

一行两个正整数 n 与 p

1 ≤ n ≤ 3×106 , n < p < 20000528

p 为质数。

Output

n 行，第 i 行一个正整数，表示 i 在模 p 意义下的乘法逆元。
Sample Input

10 13

Sample Output

第一：线性打表递推法（递推公式inv[i]=(p-p/i)inv[p%i]%p）
时间对比：
在这里插入图片描述
参考于：（https://blog.csdn.net/xuechen_gemgirl/article/details/80332859）

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll inv[20000530];
//记吧线性模板 递推公式挺简单的 （p-p/i）*inv[p%i]%p;
//数据量大的时候就明显可以看到比快速幂快了
int main(void)
{
ll a,p;
while(~scanf("%lld %lld",&a,&p))
{
memset(inv,0,sizeof(inv));
inv[0]=inv[1]=1;
for(int i=2;i<=a;i++){
inv[i]=(p-p/i)*inv[p%i]%p;
}
for(int i=1;i<=a;i++)
printf("%lldn",inv[i]);
}
return 0;
}

第二：扩展欧几里得算法
时间复杂度：在这里插入图片描述
为什么可以用扩展欧几里得求得逆元？

我们都知道模就是余数，比如12%5=12-5 * 2=2，18%4=18-4*4=2。（/是程序运算中的除）可知a%b=a-(a/b)b

那么ax≡1 (mod p)即ax-yp=1.把y写成+的形式就是ax+py=1，为方便理解下面我们把p写成b就是ax+by=1。就表示x是a的模b乘法逆元，y是b的模a乘法逆元。然后就可以用扩展欧几里得求了。
^{摘自上面链接（https://www.cnblogs.com/dupengcheng/p/5487362.html，推荐大家先看一遍）}

很多人，包括我一直无法理解扩展欧几里得算法，在我看了好多博文后才大概了解。就拿我碰到的来说：
一扩展欧几里得可以求最大公约数。
二求ax+by=gcd(a,b)的解x,y。逆元就包括其中。
x是a的模b乘法逆元，y是b的模a乘法逆元（即gcd()=1时的x/y）

现在来讲一下扩展欧几里得到底怎么来的:
其实我觉得大家只要搞懂后面递归的x,y怎么求就几乎没问题的了。
原式：ax+by=gcd(a,b)
递归：bx+(a%b)y^=gcd(a,b) 【x^和 y^就是上一步的x,y】
其中：a%b=a-(a/b)b
带入后：ay^+b ( x ^ - ( a/b ) y ^ )=gcd(a,b);
再与原式对比：ax+by=gcd(a,b)
得出：{
x=y^;
x^-(a/b ) y ^=y;
}

这就是递归过程中，x和y的由来
而当b=0时，有：(递归结束时){a=gcd(a,b),x=1,y=0}
a1+b0=a=gcd(a,b)
可得出一个特解a(最大公约数)

这样就可以得到每两个相邻状态的x和y的转化了，就可以在求gcd(a,b)的同时求对x，y求解

相信对于扩展欧几里得算法，大家会有疑问为什么b=0时x=1;y=0?
其实当达到递归基时，此时的a就是gcd(最大公约数)，b=0,那么有ax+by=a。
故x必须等于1，y可以取任何正整数。

我还是有疑问上面说了“x是a的模b乘法逆元，y是b的模a乘法逆元”
大家都统一b=0时x=1;y=0;。既然y可以取任何正整数那么我就要换一个当b=0时：x=1;y=1;这个“x是a的模b乘法逆元，y是b的模a乘法逆元”结论还是成立的。

还有一点就是建议y取0，如果取其他数组，由于y增长较快，可能会有越界的问题。

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法
{
if(b==0)
{
x=1;y=0;
return a;
//到达递归边界开始向上一层返回
}
int r=exgcd(b,a%b,x,y);
int temp=y;
//把x y变成上一层的
y=x-(a/b)*y;
x=temp;
return r;
//得到a b的最大公因数
}
//事实证明还是递推快 递推快但是耗空间
int main(void)
{
int a,p;//p是mod数
int x,y;
while(~scanf("%d %d",&a,&p))
{
for(int i=1;i<=a;i++){
exgcd(i,p,x,y);
if(x>0)
printf("%dn",x);
else
printf("%dn",x+p);//确保逆元x为正整数
}
}
return 0;
}

第三：费马小定理（快速幂qpow(a,p-2,p)）
时间复杂度对比：
在这里插入图片描述
为什么可以用费马小定理来求逆元呢？
(前提是a p 互质)
由费马小定理 a^p-1≡1(mod p) , 变形得 a * a^p-2≡1(mod p)，答案已经很明显了:若a,p互质,因为a * a^p-2≡1(mod p)且a*x≡1(mod p),则逆元x=a^p-2(mod p),用快速幂可快速求之。
摘自上面链接（https://www.cnblogs.com/dupengcheng/p/5487362.html）

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll qpow(ll a,ll b,ll p)
{
ll ans=1;
while(b)
{
if(b%2==1)
{
ans%=p;
a%=p;
ans=ans*a%p;
}
a%=p;
a=a*a%p;
b=b>>1;
}
return ans%p;
}
int main(void)
{
ll a,p;//p是质数
while(~scanf("%lld %lld",&a,&p))
{
for(int i=1;i<=a;i++){
printf("%lldn",qpow(i,p-2,p));
}
}
return 0;
}

明显在大量数据的时候递推打表快，平时普通问题用另外两个比较方便，但是由于本人数学知识薄弱不能给出证明【捂脸】
给个大佬讲解的链接：https://blog.csdn.net/guhaiteng/article/details/52123385