贝祖定理 如果 \(a\)、\(b\) 是整数，那么一定存在整数 \(x\)、\(y\) 使得 \(ax+by=\gcd(a,b)\)。 换句话说，如果 \(ax+by=m\) 有解，那么 \(m\) 一定是 \(\gcd(a,b)\) 的若干倍。（可以来判断一个这样的式子有没有解） 有一个直接的应用就是 如果 \(ax+by=1\) 有解，那么 \(gcd(a,b)=1\)。 ...

欧拉定理 欧拉定理：若 \(a\) 与 \(m\) 互质，则有 \[ a^{\varphi(m)}\equiv1(\mod m) \] 我们可以发现费马小定理其实就是欧拉定理的特殊情况。 证明的话，构造一个与 \(m\) 互质的数列操作，利用剩余系证明 扩展欧拉定理 扩展欧拉定理为 \[ a^b\equiv \begin{cases}a^{b\mod\varphi(p)},&...

斐波那契数列 \(F(0)=F(1)=1\) 或 \(F(1)=F(2)=1\)，\(F(i)=F(i-1)+F(i-2)\). 广义斐波那契数列在转移时有系数且首两项给定。 求法 注意到斐波那契数列的转移为一个矩阵乘 \[ \begin{bmatrix}F(i)&F(i-1)\end{bmatrix} \begin{bmatrix} 1&1\\ 1&...

逆元 求一个数的逆元，就是说这个数乘以它的逆元恰好等于1。在 \(\mathbb{Z}_p\) 内，设 \(a\),\(b\) 互质，则 \(a\) 的逆元记作 \(a^-1\)，定义为 \(b\)，使得 \(ab=1\)。 \(p\) 是素数时，逆元唯一存在。 \(p\) 是合数时，逆元可能不存在。 求逆元 扩展欧几里得 适用于 \(p\) 不为素数的情况。 解方程组 \(...

类欧几里得算法之所以得名是因为其算法复杂度证明与扩展欧几里得算法类似。 我认为类欧更偏向于是一种思想。 其主要思想就是寻找可以简便计算的边界，然后通过化式子将不同情况化为边界递归计算。 通过几个具体的例子，可以更好地理解其思想。 P5170 【模板】类欧几里得算法 推导 \[ f(a,b,c,n)=\sum_{i=0}^n \lfloor\frac{ai+b}{c}\rf...

线性筛 欧拉筛 线性筛（又称欧拉筛）是一种线性求素数的筛法，可以在 \(O(n)\) 的时间内找出 \(n\) 以内的所有素数。 线性筛的基本思想是，对于 \(i\) 从 \(2\) 到 \(n\) 的每个数，如果它不是素数，则枚举已筛出的每个素数，若其非 \(i\) 的因子，则将 \(i\) 乘上该素数的积标记为已被筛掉。直到枚举到 \(i\) 的最小质因子。这样，当 \(i\)...

费马小定理 对于任何互质数 \(a,p\),有 \[ a^{p-1}=1\pmod p \] 应用 求逆元： \[ a^{p-2}=a^{-1}\pmod p \]