数学相关

目录:

  1. 数论
    1. 最大公约数与最小公倍数
    2. 快速幂
    3. 逆元

数论

最大公约数与最小公倍数

最大公约数

逆元

逆元

定义:若$a\equiv \frac{1}{b}\pmod m$,则称$a$为在模$m$意义下$b$的逆元。

求法一:费马小定理($m$质数且$x$非$m$倍数)

$inv(x)=x^{m-2}$

求法二:扩展欧几里得

若$b$,$m$互质,即$exgcd(b, m, x, y)=1$,则$x=inv(b)$

求法三:线性递推

inv[1] = 1;
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;

口决:减除乘模