乘法逆元(从入门到批量求解)(正在学欧拉筛)

在做各种取余运算时，我们会发现先除和先取余的结果是不同的，这会导致计算难度的加大，乘法逆元可以解决类似的分数取余问题。

本文按照博主的学习思路排序，结论为（单个）费马小定理求乘法逆元、（单个）利用扩展欧几里得任意情况下求乘法逆元、（批量）线性递推求乘法逆元

同余的运算法则之一

定理3 ac≡bc(mod m)，且若(m,c)≡d，则a≡b(mod m/d)。——数论讲义

也就是说，同余式两边可以同除一个和模数互质的数（此时模数不变）。

费马小定理

形式1：若m是素数，则a^m≡a(mod m)。——数论讲义······①

形式2：如果m是一个素数，而整数a不是m的倍数，则有a^(m-1)≡1(mod m)。——某百科······②

由于m是一个素数，因此①到②的条件：除数a和模数m互质，等价于a不是m的倍数。

费马小定理②的推论

**a^(m-1)≡1(mod m) => a*a^(m-2)≡1(mod m) => a^(m-2)≡1/a(mod m)**

乘法逆元

对于正整数a和m，如果有ax≡1(mod m)，那么把这个同余方程中x的最小正整数解叫做a模m的逆元。

若a与m不互质，易证ax%m!=1，故a必与m互质

乘法逆元与费马小定理的推论

如果m是素数，有以下推论:

ax≡1(mod m) => x≡1/a(mod m) => x≡a^(m-2)(mod m)

(同余的传递性)

（单个）费马小定理求乘法逆元

计算(a/b)%m：

若m是素数：

将1/b替换成逆元x，即b^(m-2)%m。

答案为(a*b^(m-2))%m。

例题

51Nod 1013

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define mod 1000000007
ll n;
ll speed(ll a,ll b,ll p){
    ll cur=a,ans=1;
    while(b){
        if(b&1) ans=ans*cur%p;
        cur=cur*cur%p;
        b>>=1;
    }
    return ans%p;
}
int main(){
    cin>>n;
    ll ans=((speed(3,n+1,mod)-1)*speed(2,mod-2,mod))%mod;
    cout<<ans<<endl;
    //cout<<speed(2,mod-2,mod)%mod;
    return 0;
}```



**为了方便求任意情况的逆元，我们先来补充几个概念：**

## 欧几里得算法

log时间内求解最大公约数。

### 代码

```c++
ll gcd(ll a,llb){
    return b==0?a:gcd(b,a%b);
}```

### 证明

[辗转相除法求最大公约数算法证明](https://www.cnblogs.com/zwffff/archive/2010/08/25/1808178.html "【整理】辗转相除法求最大公约数算法证明 - 凌风有约 - 博客园")

## 贝祖定理

设a,b是整数，则存在整数x,y，使得ax+by=gcd(a,b)

## 扩展欧几里得算法

#### 求贝祖定理中x和y的解，即求使ax+by=gcd(a,b)的x和y。

我们利用gcd来求，当递归到最内层时，a=gcd(a,b)，b=0，因此x=1，y=0。

假设我们已经得到内层x1，y1，对于外层a，b有a%b=a-(a/b)*b

外层：ax+by=gcd(a,b)

内层：bx1+(a-(a/b)b)y1=gcd(a,b)

1
2
3


展开对比可得：

x=y1 y=x1-a/by1


### 代码

```c++
ll exgcd(ll a,ll b,ll &x,ll &y){//扩展欧几里得算法
    if(b==0){//递归边界 
        x=1;y=0;
        return a;
    }
    ll ret=exgcd(b,a%b,x,y);
    ll tmp=y;//求解原x,y     
    y=x-a/b*y;
    x=tmp;
    return ret;//返回gcd      
}

参考

扩展欧几里得算法详解

（单个）利用扩展欧几里得任意情况下求乘法逆元

计算(a/b)%m：

仍需要逆元存在，即b与m互质。

构造bx+my=gcd(b,m)=1，用exgcd求出来的x即为逆元。

代码与前面相同。

注意这里参数传m和-m都一样，答案要加m再%m。

参考

欧几里得算法心得(辗转相除法)

（批量）线性递推求乘法逆元

给定n,p求1~n中所有整数在模p意义下的乘法逆元。

n为3e6，p>n且为质数。

洛谷P3811 【模板】乘法逆元

此时用单个求法会超时，我们可以推导递推公式。

本垃圾博主还不会用公式编辑器，于是看这里↓

线性求逆元 - Grary - 博客园

试了试，这里p也必须是质数，还不知道为什么（逃

代码

c++ #include<bits/stdc++.h> using namespace std; #define ll long long const ll MAXN=3e6+20; ll inv[MAXN]; ll n,mod; void preinv(ll num,ll p){ inv[0]=inv[1]=1; for(ll i=2;i<=num;i++){ inv[i]=(p-p/i)*inv[p%i]%p; } } int main(){ cin>>n>>mod; preinv(n,mod); for(ll i=1;i<=n;i++){ printf("%lld\n",inv[i]); } return 0; }