KV熵的Blog

取模(mod)

运算符：%

$a \% b$：$a \div b$的余数

对于取模，有以下性质：

• $(a+b)\bmod{p} = ((a\bmod{p})+(b\bmod{p}))\bmod{p}$
• $(a-b)\bmod{p} = ((a\bmod{p})-(b\bmod{p}))\bmod{p}$
• $(a \times b)\bmod{p} = ((a\bmod{p}) \times (b\bmod{p}))\bmod{p}$

但对于相除再取模，就得另想办法，这就说到了我们的逆元

逆元

注：逆元指的一般是乘法逆元，至于其它的逆元我也不太了解

如果有一个数 $b'$ ，满足$b \times b' \bmod{p} = 1$，我们则称$b'$是$b$的乘法逆元

特别的，只有在$gcd(b,p) = 1$（即$b$与$p$互质）的前提下才存在乘法逆元

有了逆元，我们就可以将相除再取模转换为相乘再取模

$a \div b \bmod{p} = a \div b \times 1 \bmod{p} \\= a \div b \times (b \times b') \bmod {p} \\= a \div b \times b \times b' \bmod{p} \\= a \times b' \bmod{p}$

（$b'$是$b$的乘法逆元）

那么逆元怎么找呢，往下看

费马小定理

当$p$为质数时，对于任意的$b$，满足$b^{p-1}\bmod{p} = 1$

我们可以拆解成$b \times b^{p-2} \bmod{p} = 1$

所以$b$的乘法逆元为$b^{p-2}$

但如果$p$不为质数，则需要使用欧拉定理

欧拉定理

$b^{\varphi(p)}\bmod{p} = 1$

$\varphi(p)$又可以写作$phi(p)$，欧拉函数，表示的是1~p中与$p$互质的数的个数

但是，我们发现，如果暴力求$\varphi(p)$那么会复杂度会非常之高

那么这里提供一个新的$\varphi(p)$的求法

我们可以把$p$做一个质因数分解，得到：$p = p_1 \times p_2 \times ... \times p_m$

那么$\varphi(p) = p \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times ... \times \frac{p_m-1}{p_m}$

逆元打表

如果我们想要一次性求一个数列的逆元，我们可以使用递推法

对于一个质数$p$，求从1~n中$\pmod{p}$的乘法逆元，我们有以下递推公式：

$\begin{cases}inv_1=1\\inv_i=(p-p \div i) \times inv_{p\bmod{i}}\bmod{p}\end{cases}$

注：$inv_i$表示$i$的乘法逆元$\pmod{p}$

拓展欧几里德找逆元

要求$a$的逆元$\pmod{p}$，我们可以求到一组$x,y$使得$a \times x+p \times y = gcd(a,p)$，则$(x \bmod{p}+p)\bmod{p}$

证明：

由于逆元存在的条件为$gcd(a,p)=1$，所以我们可以直接将$a \times x+p \times y = gcd(a,p)$写成$a \times x+p \times y = 1$

随后，我们在等式两边同时模一个$p$，因为1模任何正整数均为1，因此可以的出$(a \times x+p \times y) \bmod{p} = 1$

根据取模的分配率可以及将其写成$a \times x \bmod{p} +p \times y \bmod{p} = 1$

而因为$p \times y$一定是$p$的倍数，所以$p \times y \bmod{p} = 0$

因此，我们可以将$a \times x \bmod{p} +p \times y \bmod{p} = 1$写成$a \times x \bmod{p} = 1$

所以$x$则为$a$的乘法逆元

不过，此时$x$并不一定就是正数，所以我们需要通过$(x \bmod{p}+p)\bmod{p}$将其转换为非负数

所以，得证

证明出这个之后，我们就可以通过拓展欧几里德来找逆元，比欧拉定理还快。由于我拓展欧几里德不是特别熟悉，这里放个代码吧

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return d;
}
int inv(int a,int p){
    int x,y;
    exgcd(a,p,x,y);
    return (x%p+p)%p;
}