OI 数论总结

数论学习笔记

最大公约数：\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 为质数

模板题：