乘法逆元模板题

六行（）AC代码

#include<bits/stdc++.h>
long long n, p, inv[3000010];
int main( void ){
    std::scanf( "%lld%lld", &n, &p ); inv[1] = 1; std::printf( "%lld\n", inv[1] );
    for( int i = 2; i <= n; i++ ) std::printf( "%lld\n", inv[i] = ( ( p - p / i ) * inv[p % i] ) % p );
}

乘法逆元是啥？

“逆”可以理解为是抵消之前的运算效果

$ e. g. $

$ a = a + b - b$ 那么 $+ b$ 就叫做 $- b$ 的逆

同理 $ a = a * b * \frac{1}{b} $ 那么 $\frac{1}{b}$ 就叫做 $* b$ 的逆

很好理解吧

那么现在请思考，我们知道$ ( a * b )$ $mod$ $p = （ a$ $mod$ $p ) * ( b$ $mod$ $p )$，那么 $ \frac{a}{b} $ mod $ p $ 是否等于 $( a$ $mod$ $ p ) * ( b$ $mod$ $p )$呢

显然不等于

怎么办呢？我们只能找一个$x$，使得$\frac{a}{b}$ $mod$ $ p = a * x $ mod $ p$

此时$ x$ 叫做 $b$的乘法逆元，表示为$b * x\equiv 1 $( $mod$ $p$ )，叫做$b * x$ 与 1 关于 $ p $ 同余， $\equiv$的意思是$b * x$ $mod$ $ p = 1$ $mod$ $p$，也可以写成 $ ( b * x - 1 ) / p = 0 $

为啥是$ b * x \equiv 1$ 而不是$ a * x \equiv 1 $？？？

既然$b * x$ 和 1 同余了，那么求余时这俩就是等价的了，所以$ a / b * 1$ $mod$ $ p = a / b * b * x$ $mod$ $ p = a * x$ $mod$ $p$

注意：存在的充要条件是 $a ,p$互质

咋求乘法逆元？

求单个数的乘法逆元，可以用拓展欧几里得（不知道的戳这里）

$a * x \equiv 1 ( mod $ $p)$ 可写成 $ a * x - p * y = 1$

此时，这一不定方程就可以用拓展欧几里得解了

另外，前面很$dalao$也写了，可以用费马小定理加速，

因为$ a ^ {p- 1} \equiv 1 (mod$ $p)$，很明显可以写成

$a * a ^ {p - 2} \equiv 1 (mod$ $p)$，那么逆元就求出来了，可以用快速幂加速

但是太麻烦了，乘法逆元可以线性预处理

$ inv[i] = ( p - \frac{q}{i} ) * inv[p $ $mod$ $i] $ $mod$ $p$

试着证明

$i * inv[i]$ $mod$ $p$

$= i * (p - \frac{p}{i}) * inv[p $ $mod$ $i]$ $ mod $

$= i * (p - \frac{p-p MOD i}{i}) * inv[p $ $mod$ $i]$ $ mod $

//因为分子打不了$mod$,所以用MOD表示了

$=( p $ $mod$ $i )* inv[p $ $mod$ $i]$ $ mod $ $p$

$= 1$

适用范围

$i < p, p$为质数（只有p为质数时才能保证小于p的数全部与p互质）
$inv[i] = inv[i $ $mod$ $p]$

对于$ i > p $ 且 $ i $ 不整除 $p$ 时

实现代码如下

inv[1] = 1;
for ( int i = 2; i <= n; i++ ) {
    inv[i] = ( p - p / i ) * inv[p % i] % p;
}

return; // 功德圆满

逆元

乘法逆元