求乘法逆元的几种方法

[toc]

求模意义下一个数的乘法逆元有多种方法.

方法1

利用裴蜀定理(扩展欧几里得算法)。

直接解线性方程$ax+bp=1$, 可知$a^{-1}=x$.

方法2

利用费马小定理。

对任意素数$p$, 若$a<p$, 则 \(a^{p-1}\equiv 1(\mod p)\)

推至$a^\equiv a^{-1}(\mod p)$

所以使用快速幂算法求得模意义下的$a^$就可以得到$a$的乘法逆元

方法3(线性批量求逆元)

使用了一个巧妙的递推构造.

首先我们知道 \(p=aq+r, 0 \le r < a\), 其中$q=\lfloor \frac p a\rfloor$

由此 \(aq+r\equiv 0 (\mod p)\)

由此$aa^{-1}r^{-1}q + ra^{-1}r^{-1} \equiv 0 (\mod p )$

由此$-r^{-1}q\equiv a^{-1}(\mod p)$

上式中$r < a$, 所以, 对于一个数, 我们总可以利用比其小的数的逆元推出它的逆元.

又有$1^{-1} =1$

由此我们建立了一个线性递推方法.

下面会给出这种方法的程序实现.

/*
    Problem : [Luogu]P3811
    Content : 给定n,p, 求1~n中所有整数在模p意义下的乘法逆元。
    Author  : shleodai (blog : www.cnblogs.com/Eroad)
*/
#include<bits/stdc++.h>
using namespace std;

#define ll long long 
const int maxn = 3e6+5;
int inv[maxn], p, n;
signed main(){
    scanf("%d %d", &n, &p);
    inv[1] = 1;
    for(int i = 2; i <= n; i++) inv[i] = (p - (ll) (p/i) * inv[p%i] % p) % p;
    for(int i = 1; i <= n; i++) printf("%d\n", inv[i]);
    return 0;
}

求乘法逆元的几种方法

原文：https://www.cnblogs.com/Eroad/p/11755430.html