威尔逊定理

OI

定理内容

$$
p是素数\Leftrightarrow (p-1)!\equiv-1\ (\text{mod}\ p)
$$

证明(口胡)

考虑$[1,p-1]$内的所有整数,他们在$\text{mod}\ p$意义下一定是有逆元的,且他们的逆元一定是小于等于p的

矩阵快速幂

OI
矩阵快速幂.md

前置技能

矩阵乘法

复杂度为$O(n^3)$,有复杂度稍低的分治写法,不过意义不大(毕竟你的矩阵这么小)

$A,B$是两个矩阵,其中$A$是$m\times n$的矩阵,$B$是$x\times y$的矩阵

当且仅当$n=x$时$A\cdot B$有意义。

裴蜀定理

OI

定理内容

关于$x,y$的二元一次方程$ax+by=m$有解,当且仅当$m$是$d$的整数倍,其中,$d=\gcd(a,b)$

读完上面这句话,你一定会觉得这是什么辣鸡定理,感觉好没用的样子。

其实裴蜀定理还用后半部分。