数论学习笔记

前置知识

最大公约数：

\gcd(x,y)=\gcd(y \bmod x,x)

扩展欧几里得：

ax+by=\gcd(a,b)

OI 中常用的公式其实主要只有三个：

还有它们的扩展。

下面是公式。

中国剩余定理：同余方程组 $\begin{aligned} \left\{\begin{matrix} \mathrm{x} \equiv \mathrm{a}_{1}\left(\bmod \mathrm{~m}_{1}\right) \\ \mathrm{x} \equiv \mathrm{a}_{2}\left(\bmod \mathrm{~m}_{2}\right) \\ \ldots \\ \mathrm{x} \equiv \mathrm{a}_{\mathrm{k}}\left(\bmod \mathrm{~m}_{\mathrm{k}}\right) \end{matrix}\right. \end{aligned}$ 的解为：令 $M=\prod_{i=1}^{k} m_i,M_i=\frac{M}{m_i},M_i^{-1} 为 M_i 模 m_i 的逆元$ ，则 $x \equiv (\sum^{k}_{i=1} m_iM_iM_i^{-1})(\bmod m)$
卢卡斯定理： $C^n_m \bmod p=C^{n \bmod p}_{m \bmod p} \times C^{n/p}_{m/p}$ ， $p$ 为质数

模板题：