To boldly go where no one has gone before.

【学习笔记】逆元

2019-03-30 12:01:26


定义

求解除法取模运算时,令:$$a\div b (\mod p)=a\times b^{-1}(\mod p)$$ 其中:$$b \times b^{-1}\equiv 1(\mod p)$$

正确性证明

$$\Rightarrow (a\div b) \mod p=(a\div b)\times 1\mod p$$$$\because b\times b^{-1} \mod p=1,$$$$\therefore \text{原式}=(a\div b)\times(b\times b^{-1})\mod p=(a\times b^{-1})\mod p$$$$\Rightarrow (a\div b)\mod p=(a\times b^{-1})\mod p$$

定理

$a\div b\mod p=a\times b^{-1} \mod p$,其中$b^{-1}$为$b$的逆元。

逆元求法

费马小定理求法

首先要知道费马小定理

如果$p$为质数,且$gcd(a,p)=1$,则:$$a^{p-1}\equiv1(\mod p)$$ 对这个式子进行变形:$$a\times a^{p-2}\equiv1(\mod p)$$ 所以当$gcd(a,p)=1$时,$a$关于$p$的逆元就是$a^{p-2}$。

继续推导,则:$$a\div b \mod p=(a\mod p)\times (b^{-1}\mod p) \mod p$$$$(\text{其中}b^{-1}=b^{p-2})$$ 因此利用这种方法,逆元就可以用快速幂算出来。

$\textbf{exgcd}$求法 $(p$为质数$)$

设$ax+py=gcd(a,p)=1$的解为$x$和$y$,那么$a$关于模$p$的逆元就是$(x\mod p+p) \mod p$。


代码

#include<bits/stdc++.h>
using namespace std;

inline int ExGcd(int a, int b, int &x, int &y) {
    if(!b) {
        x = 1, y = 0;
        return a;
    }
    int gcd = ExGcd(b, a % b, y, x);
    y -= a / b * x;
    return gcd;
}

int main() {
    int a, p, x, y;
    scanf("%d%d", &a, &p);
    ExGcd(a, p, x, y);
    x = (x % p + p) % p; 
    printf("%d\n", x);
    return 0;
}

线性递推求法

这个方法适用于求 P3811 这种$[1,n]$范围内的逆元,复杂度为$O(n)$。

设$p=k* i+r$,其中$k=\biggl\lfloor\ \frac pi \biggr\rfloor=p/i,r=p\mod i$,则:$$k* i+r\equiv 0(\mod p)$$ 两边同乘$i^{-1}$和$r^{-1}$,得:$$k* r^{-1}+i^{-1}\equiv 0(\mod p)$$$$\Rightarrow i^{-1}\equiv -k* r^{-1}(\mod p)$$ 把$k$和$r$的定义带入,即可得:$$i^{-1}\equiv -(p/i)* (p\mod i)^{-1}$$$$\Rightarrow i^{-1}=(p-p/i)* (p\mod i)^{-1}\mod p$$$$\therefore \text{由}(p\mod i)\text{的逆元即可推知}i\text{的逆元}.$$


代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 10;
long long inv[MAXN];

int main() {
    int n, p;
    scanf("%d%d", &n, &p);
    inv[1] = 1;
    printf("1\n");
    for(register int i = 2; i <= n; i++) {
        inv[i] = (p - p / i) * inv[p % i] % p;
        printf("%lli\n", inv[i]);
    }
    return 0;
}

还有一种简单的处理方法:$$a/b\%c=(a\%(b*c))/b$$


参考资料

除法逆元