莫比乌斯反演可以用于优化一类式子的计算。 莫比乌斯函数 定义 莫比乌斯函数的定义如下： $$ \mu(n)= \begin{cases} 0 & \exists\ p^2 \mid n \wedge p>1\\\\ (-1)^k & n=\prod_{i=1}^{k} p_i \end{cases} $$ 也就是说，如果 $n$ 含有平方约数，则 $\mu(n)=0$，否则 $\mu(n)=(-1)^k$，其中 $k$ 为 $n$ 中的本质不同的质约数个数。 性质 积性函数 $\mu(n)$ 为积性函数，证明如下： 设 $a,b$ 满足 $\gcd(a,b)=1$。 若 $a,b$ 其中一个数含有平方约数，则它们的乘积也一定含有平方约数，此时它们的莫比乌斯函数值都为 $0$，即 $\mu(ab)=\mu(a)\mu(b)=0$。 否则 $a,b$ 都不含有平方约数，则设它们的质约数个数分别为 $k_a,k_b$，则 $\mu(a)=(-1)^{k_a},\mu(b)=(-1)^{k_b}$，因为满足 $\gcd(a,b)=1$，故 $ab$ 的质约数个数为 $k_a+k_b$，$\mu(ab)=(-1)^{k_a+k_b}=(-1)^{k_a}(-1)^{k_b}=\mu(a)\mu(b)$。 Q.E.D. 与常数函数的卷积 这个性质十分重要，是反演的基础。这个性质可以写成 $I * \mu= \epsilon$，或者： $$ \sum_{d\mid n}I(\frac{n}{d})\mu(d)=\epsilon(n) $$ 经常简记为： $$ \sum_{d\mid n} \mu(d) = [n=1] $$ $\epsilon$ 是 Dirchlet 卷积的单位元函数。...

解各种同余方程是同余问题的一个重要部分，本文介绍各种同余方程的求解方法。 二元线性不定方程 形式 不定方程的范围很广泛，只要没有确定的解的方程都可以叫不定方程。本文主要讨论数论中的不定方程。 $$ ax+by=c\ (a,b,c,x,y\in \mathrm{Z}) $$ 形如上面这种形式，满足各项的系数和解均为整数的方程就是数论中的不定方程。 求解 Theorem 1：$\forall a, b \in \mathrm{Z}$，一定存在 $x,y\in \mathrm{Z}$，使得 $ax+by=\gcd(a,b)$。 这个定理又叫做裴蜀定理，根据这个定理，可以得出不定方程 $ax+by=c$ 有解的充要条件就是 $\gcd(a,b)\mid c$。记 $d=\gcd(a,b)$，则我们可以先求出 $ax'+by'=d$ 的解，再令 $x=\frac{c}{d}x',y=\frac{c}{d}y'$，就得出原方程的一组解。 求 $x',y'$ 的过程可以用扩展欧几里得算法，即 exgcd 解决。 Theorem 2：若 $\gcd(a,b)=1$，且 $x_0,y_0$ 是方程 $ax+by=c$ 的一组解，则该方程的通解为 $x=x_0+kb,y=y_0-ka$，其中 $k\in \mathrm{Z}$。 换句话说，$x,y$ 这两个解是具有周期性的。根据这个定理，我们知道一定有一个 $x\in [0,b)$，而对于方程 $ax+by=c$，则一定有一个 $x\in [0,\frac{b}{\gcd(a,b)})$，由此可以求一个不定方程的一个元的最小非负整数解，具体地，假设知道了一个解 $x_0$，则最小非负整数 $x=(x_0 \bmod m + m) \bmod m$，其中 $m=\frac{b}{\gcd(a,b)}$。 总结一下，求解二元线性不定方程 $ax+by=c$ 的流程如下： 求出 $ax+by=\gcd(a,b)$ 的一组解 $x',y'$，并根据 $\gcd(a,b)\mid c$ 判断方程有无解 令 $x=\frac{c}{\gcd(a,b)}x',y=\frac{c}{\gcd(a,b)}y'$，$x,y$ 为 $ax+by=c$ 的一组解 若需要求 $x$ 的最小非负整数解，则将 $x=(x_0 \bmod m + m) \bmod m$ 作为最终的答案，其中 $m=\frac{b}{\gcd(a,b)}$ 线性同余方程 形式 $$ ax \equiv c \pmod{p} $$ 形如这样的方程，就被称线性同余方程。...

Burnside 引理和 Pólya 定理主要用于解决计算本质不同方案数的计数问题。 群论 基本定义 群可以看成是一个由集合和某个二元运算组成的二元组 $(S,\cdot)$，这里的 $\cdot$ 就代表一个二元运算，这个二元运算需要满足结合律、存在单位元和逆元。群有很多的种类，比如置换群、循环群、矩阵群等，其中置换群就是我们接下来要介绍的。 性质 若一个二元组 $(S,\cdot)$ 是群，则它满足以下性质： 封闭性：$\forall x,y\in S$，若 $z=x\cdot y$，则 $z\in S$ 结合律：$\forall x,y,z\in S$，$(x\cdot y)\cdot z=x\cdot (y \cdot z)$ 单位元：存在唯一一个元素 $e \in S$ 满足 $\forall x \in S$，$e\cdot x=x$ 逆元：$\forall x \in S$，都可以找到唯一一个元素 $x^{-1}$ 满足 $x \cdot x^{-1} = e$，这个元素称为 $x$ 的逆元 举一个简单的例子，$(\mathrm{Z},+)$ 就是一个群，无论取哪两个元素进行加法运算，结果仍然是整数；加法满足结合律；单位元 $e = 0$；任意一个元素 $x$ 的逆元 $x^{-1} = -x$。 置换与置换群 置换的基本定义 顾名思义，置换群就是置换组成的群。置换可以看成一个有限集合到自身的双射，具体一点，假设有两个长度相同的集合 $p,q$（这里假设集合可以有序），则置换 $f$ 作用于 $p$ 就是生成一个新的集合 $p'$，满足 $p'_i=p\_{q_i}$。...

欧拉函数 $\varphi(n)$ 是一个重要的数论函数，它表示 $[1, n]$ 中与 $n$ 互质的数的个数。 欧拉函数性质 积性函数 积性函数的定义是：如果一个函数 $f(n)$ 满足 $\gcd(a,b)=1$ 时 $f(ab)=f(a)f(b)$，则 $f(n)$ 为积性函数。 若无需 $\gcd(a,b)=1$ 就有 $f(ab)=f(a)f(b)$，则它为完全积性函数。 $$ n = \prod p_i^{c_i}\\\\ f(n) = \prod f(p_i^{c_i}) $$ 一般来说，各种积性函数都是可以使用欧拉筛计算出来的，尽管方法各不相同。 $\varphi(n)$ 也是积性函数，证明就省略了。 计算公式 因为 $\varphi(n)$ 是积性函数，所以我们可以先研究 $\varphi(p^k)$ 怎么计算。$p^k$ 的约数有 $1, p, p^2, \dots, p^k$，而 $p^2, \dots, p^k$ 都含有 $p$ 这个约数，如果一个数不与 $p^k$ 互质，则一点有 $p$ 这个约数，我们只有知道小于等于 $p^k$ 的数中 $p$ 的倍数有多少即可。由此得出 $\varphi(n) = p^k - \frac{p^k}{p} = p^k - p^{k-1}=p^k\frac{p-1}{p}$。...

拉格朗日插值是众多插值算法中的一种，插值是通过一些点来求出过这些点的多项式函数的过程。 算法思想 构造函数 给出 $n + 1$ 个点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n),(x_{n+1},y_{n+1})$，要求出过这些点的 $n$ 次多项式函数（也称该函数的度为 $n$），先考虑对每个点构造一个函数，第 $i$ 个点的函数为 $f_i(x)$，满足： $$ f_i(x) = \begin{cases} y_i & x = x_i\\\\ 0 & x \ne x_i \end{cases} \ (x\in \\{x_1,x_2,\dots,x_n,x_{n+1}\\}) $$ 最后将这些函数组合为最终的函数： $$ f(x) = \sum_{i=1}^{n+1}f_i(x) $$ 接下来就是找到一种合适的形式来表示 $f_i(x)$ 的分段规定，可以让 $f_i(x)$ 含有一些因式，满足 $x=x_j,j\ne i$ 时，其值为 $0$，$x=x_i$ 时，其值为 $y_i$。显然下面这种满足条件： $$ f_i(x) = y_i \prod_{i\ne j} \frac{x-x_j}{x_i-x_j} $$ 所以最终的 $f(x)$ 的解析式为： $$ f(x) = \sum_{i=1}^{n + 1} y_i \prod_{i\ne j} \frac{x-x_j}{x_i-x_j} $$ 求单个函数值的时间复杂度是 $\Theta(n^2)$。...

高斯消元主要用于求解线性方程组的解，同时可以解决某些有后效性的 DP 问题， 算法思想 增广矩阵 为了更方便地求解方程组，可以将系数和常数项放入矩阵，接下来就可以用一些矩阵的操作来消元了。 比如有一个方程组如下： $$ \begin{cases} 3x+2y+3z=10\\\\ 3x+y+4z=12\\\\ x+y+z=4 \end{cases} $$ 我们可以这么用矩阵表示: $$ \begin{bmatrix} 2 & 2 & 3 \\\\ 3 & 1 & 4 \\\\ 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} 10 \\\\ 12 \\\\ 1 \end{bmatrix} $$ 在理论分析和实现代码时，为了方便，通常把两个矩阵拼在一起，这个矩阵就是增广矩阵： $$ \begin{bmatrix} 2 & 2 & 3 & 10 \\\\ 3 & 1 & 4 & 12 \\\\ 1 & 1 & 1 & 1 \end{bmatrix} $$ 增广矩阵的第 $i$ 行代笔第 $i$ 个方程，第 $i$ 列表示第 $i$ 个未知数的系数或常数项，接下来用 $x_i$ 表示第 $i$ 个未知数。...