基础算法与数学总结 【第四部分 数学】

· · 闲话

基础算法与数学总结 【第四部分 数学】

1 质数

定义1.0.1 质数

质数是无法被除了1与它本身的自然数整除的数。

本章略：质数判定、质因数分解（两个都是试除法）

1.1 筛法

当然，筛法可不止用来筛个质数，注意到很多的常用函数都跟质因子有关系，筛法基于累计质因子的方法筛掉合数，累计的时候其实也就知道了合数的其中一个质因子。

筛法现阶段常用两种，即埃氏筛和线性筛。

埃氏筛就是直接累积质因子，这样可能出现重复，而线性筛通过从大到小累计质因子来唯一确定唯一分解。

时间复杂度证明略，这超出了讨论范围。

埃氏筛的时间复杂度是 \mathcal{O}(N \log \log N) ,线性筛的复杂度即线性阶 \mathcal{O}(N)

定理1.1.1 算术基本定理

任何一个大于1的正整数都能唯一分解成有限个质数的乘积，可以写作：

N=p_1^{c_1}p_2^{c_2}\ldots p_m^{c_m}

其中，c_i\in \mathbb{N}^+,p_i 都是质数，且 p_1<p_2<\ldots < p_m 。

这条定理把对于自然数的研究转化为对质数的研究。

同时这里还要提到质数的分布：1至N中质数个数约为 \mathcal{O}(\frac{N}{\log N})

2 约数

定义2.0.1 约数与倍数

如果整数n除以整数c的余数为0，则称c是n的约数，n是c的倍数，记作 c\mid n ，即c整除n，否则称c不能整除n，记作 c \nmid n 。

试除法与倍数法的推论

这两个推论是对算法过程的分析而得出的。

推论2.0.1 算术基本定理的推论
$$ (c_1+1)\times (c_2+1)\times \ldots\times (c_m+1)=\prod_{i=1}^{m}(c_i+1) $$ $N$ 的所有正约数的和： $$ (1+p_1+p_1^2+\ldots+p_1^{c_1})\times\ldots\times(1+p_m+p_m^2+\ldots+p_m^{c_m})=\prod_{i=1}^m(\sum_{j=0}^m(p_i)^j $$ ---------- 证明略，本质上是排列组合。 ### 2.1 最大公约数 （定义略） ##### 定理2.1.1 $$ \forall a,b \in N \quad \gcd(a,b)\times \operatorname {lcm}(a,b)=a\times b $$ ----------------- 哎算了，还是不要为难自己打证明过程了。 对于gcd和lcm的证明很多都跟质因数分解有关，这个也可以这么理解。 求解gcd的方式有两种以下： ##### 定理2.1.2 九章算术·更相减损术 $$ \forall a,b\in \mathbb{N},a\ge b\quad \gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b) $$ $$ \forall a,b\in \mathbb{N}\quad \gcd(2a,2b)=2\gcd(a,b) $$ ---------------- 根据定义，后者显然成立。而来证明前者。可推得： $$ \forall d\mid a\wedge d\mid b\quad \text{令 }a=k_a\times d,b=k_b\times d $$ 则有 $$ a-b=d\times(k_a-k_b) $$ 则可知$d\mid (a-b)$ 。那么对于a，a-b同理，则它们的最大公约数当然相等。 ##### 定理2.1.3 欧几里得算法 $$ \forall a,b\in \mathbb{N},b\ne 0 \quad \gcd(a,b)=\gcd(b,a \bmod b) $$ -------------------- 证明略。总之，对于这些证明都是要回归到讨论他们公约数集合的情况。 同样，对应到了题目里，还是要讨论他们质因子的情况。 gcd的实现： ```cpp int gcd(int a,int b){ return b?gcd(b,a%b):a; } ``` ### 2.2 互质与欧拉函数 ##### 定义2.2.1 互质 $\forall a,b\in \mathbb{N}$ ，若 $\gcd(a,b)=1$ ，则称 $a,b$ 互质。 ##### 定义2.2.2 欧拉函数$\varphi 1\sim N$ 中与 $N$ 互质的数的个数被称为欧拉函数，记作 $\varphi(N)
推论2.2.1 欧拉函数的计算式

若在算术基本定理中 N=p_1^{c_1}p_2^{c_2}\ldots p_m^{c_m} ，那么存在:

\varphi(N)=N\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\times \ldots \times \times \frac{p_m-1}{p_m}=N\times \prod_{\text{质数}p\mid N}(1-\frac{1}{p})

由欧拉函数的定义，我们知道1\sim N 有 N 个数，如果有某一个数 a 含有与 N 相同的质因子，那么就需要排除这个数。这启发我们使用容斥原理计算应该排除的数。

定义2.2.3 积性函数

如果当 a,b 互质时，有 f(ab)=f(a)\times f(b) ，那么称函数 f 为积性函数。

推论2.2.2-2.2.7 欧拉函数的性质

  1. 对于所有大于1的n，1到中与n互质的数之和为 \frac{n\times \varphi(n)}2

  2. 欧拉函数 \varphi 是积性函数

  3. 若 f 是积性函数，则在算术基本定理中 n=\prod_{i=1}^mp_i^{c_i} ，则 f(n)=\prod_{i=1}^{m}f(p_i^{c_i})

  4. 设 p 为质数，若 p\mid n 且 p^2\mid n ，则 \varphi(n)=\varphi(\frac{n}{p})\times p

  5. 设 p 为质数，若 p\mid n 但是 p^2\nmid n ，则 \varphi(n)=\varphi(\frac{n}{p})\times(p-1)

  6. \sum_{d\mid n}{\varphi(d)}=n

简单证明：

  1. 由于以上九章算术的算法，若有一个数 x 与 n 互质（即最大公约数为1），那么就一定有 n-x 也是与 n 互质。所以每一对的平均数都是 \frac{n}{2}，总体也是这样。

  2. 对a,b 分解质因数然后带进 \varphi 的计算式

  3. 由定义易得

  4. 由原命题，n中含一个以上质因子p，则 \frac{n}{p} 只是少了一个p，其它不变，使用欧拉函数计算式相除得到

  5. 由2易得

  6. 构造函数f等于上式左边，乘开然后利用性质2得f是积性函数，证明f对于单个质因子满足f(p^m)=p^m ，得证。

这些性质不知道会在什么时候有用，无论如何，最先考虑的都是建模。

3 同余

定义3.0.1 同余

若整数 a 与整数 b 除以正整数 m 的余数相等，则称 a,b 模 m 同余，记作 a\equiv b\pmod m

> 通俗地说，同余类就是所有模m余a的整数 **注意：** 余数通常的定义是这样的：若非负整数 $r$ 满足 $a=kb+ r$ ，其中 $a,b,k\in \Z$ ，则称r是a模b的余数，这称为最小非负余数，C++中的实现于此不同，要使得a%b的结果变为数学中的定义，使用 $(a\bmod b+b)\bmod b$ 。同时注意**如果没有特别说明，模数总是正整数。** 而完全剩余系通俗来讲就是把所有整数按照模m的余数分成m类。 简化剩余系就是忽略余数非质数的完全剩余系。 ##### 定理3.0.1 简化剩余系关于模m乘法封闭。 --------------- ##### 推论3.0.1 同余的性质 1. 自反性：$a\equiv a\pmod m$ 。 2. 对称性：若 $a\equiv b\pmod m$ ，则 $b\equiv a\pmod m$ 。 3. 传递性：若 $a\equiv b\pmod m$ ，$b\equiv c\pmod m$ 那么 $a\equiv c\pmod m$ 。 4. 同余式相加减：若$a≡b\pmod m$ ， $c≡d\pmod m$ ，则 $a±c≡b±d\pmod m

  1. 同余式相乘：若 a≡b\pmod m ， c≡d\pmod m ，则 a\times c≡b\times d\pmod m

  2. a\equiv b\pmod m \implies m\mid (a-b)

  3. 若 a\equiv b\pmod m 则 ak\equiv bk\pmod m

  4. 若 ak\equiv bk\pmod m 且存在 \gcd(k,m)=1 则 a\equiv b\pmod m

证明略。总共的方法就是将同余式化成余数的定义式。

定理3.0.2 费马小定理

若 p 是质数，则对于任意整数 a ， 有 a^p\equiv a \pmod p 。

定理3.0.3 欧拉定理

若正整数 a,n 互质，则 a^{\varphi(n)}\equiv 1\pmod n 。

利用“同一法”，证明简化剩余系的可替换性，构造替换后的同余式，两边同时除以得到欧拉定理。

然后费马小定理就是欧拉定理的一个特殊情况。

推论3.0.2 欧拉定理的推论

若正整数 a,n 且 a\perp n ， 则对于任意正整数 b ， 有 a^b\equiv a^{b\bmod \varphi(n)}\pmod n

证明略。

对于一般的加减乘运算，我们都可以将操作数先模再算。然后这条推论告诉我们对于乘方运算也可先把底数模p再把指数模 \varphi(n) 然后计算。

推论3.0.3

若正整数 a,n 互质，则满足 a^x\equiv 1\pmod n 的最小正整数 x_0 是 \varphi(n) 的约数。

反证法证明，略。

3.1 扩展欧几里得算法

定理3.1.1 裴蜀定理

对于任意整数 a,b ，存在一对整数 x,y ，满足 ax+by=\gcd(a,b) 。

证明思路如下，数学归纳法：

  1. 论证基点：对于 \gcd(a,0) 有 x=1,y=0 满足

  2. 证明若对于 \gcd(b,a\bmod b) 成立，则对于 \gcd(a,b) 成立。

    • 由于定理2.1.3，\forall b>0 ，\gcd(a,b)=\gcd(b,a\bmod b) 。

    • 那么将 \gcd(b,a\bmod b) 设参变换成为裴蜀定理的形式然后就能推知这样的x,y存在

同时这也告诉了我们如何求解这样的式子。

对于更加一般的式子只需要运用等式的基本性质变换即可。

定义3.1.1 乘法逆元

乘法逆元是满足这样式子 ab\equiv 1\pmod m 的整数b，记作 a^{-1}\pmod m

所以乘法逆元就是在模意义下消除乘法影响的一个数。这就是除法的含义。

对于大数的除法在模p意义下，不能分子分母模之后再计算，但是可以计算出分母的乘法逆元转化为乘法。

若模数p是质数，那么由费马小定理得 b^{p-2} 就是b的乘法逆元。

如果只是保证 b,p 互质，那么就需要求解 bx\equiv 1\pmod m 来计算。

需要注意当分母与模数不互质时，乘法逆元不存在，注意特判。

3.2 线性同余方程

由推论3.0.1.6并设参将线性同余方程化为裴蜀定理。

方程的解法略。方程的通解是所有模 \frac{m}{\gcd(a,m)} 与x同余的整数。

定理3.2.1 中国剩余定理（CRT）

已知正整数 n_1, \dots, n_k 两两互质，定义 N=\prod_{i=1}^k n_i 和 N_i=\frac{N}{n_i} 又已知整数 a_1, \dots, a_k ，那么同余方程组 。

\begin{cases}x\equiv a_1 \pmod{n_1}\\ x\equiv a_2 \pmod{n_2}\\ \vdots\\ x\equiv a_k\pmod{n_k}\end{cases}

在 0\le x < N 范围内有且仅有一个解 。 因为 \gcd(n_i, N_i)=1\quad \forall i\in\{1, 2, \dots, k\} ，由裴蜀定理我们能够得到对于每一个 i\in\{1, \dots, k\} 存在整数 M_i, m_i 使得 M_iN_i+m_in_i=1\\ 。 通过扩展欧几里得算法求出 M_1, \dots, M_k ，这个同余方程组的一个特解就可以表示为 x_0=\sum_{i=1}^k a_i M_iN_i \\ 通解可以表示为 x=Nq+x_0\\ ，其中 q\in \mathbb{Z} 是任意整数

证明略。CRT可以使用EXCRT替换，后者适应的情况更多，同样都要解k个线性同余方程。

EXCRT考虑使用数学归纳法，假如已经求出前i-1个方程的特殊解x，则前i-1个方程的通解是：x+im(i\in\Z) ，其中m是前i个方程模数的最小公倍数。然后设一个参t，试在 \Z 中解出一个t满足前i个方程，然后这就是前i个方程的一个特解。重复以上操作直至求解所有线性同余方程。

4 矩阵乘法

矩阵乘法的定义太复杂，说个简单的：

矩阵乘法可用来加速递推。之前我们在**图论进阶总结**里面的一个例题里说过： > 当然，这题DP意味是浓重的，如果获得了从i->k经过p条的最短路和从k->j经过q条的最短路 > > 那么就可以获得从i->j经过p+q条的最短路。如何合并呢？考虑枚举矩阵里的内容然后取min。然后又注意到如果合并经过p条和经过q条的矩阵得到p+q，那么矩阵快速幂就显而易见了。 > > 只要有某种方法合并两个矩阵使得**阶段信息**是这种“和/积变换”的，都可以矩阵快速幂优化。 当然，书上已有总结，笔者再加以提炼： 1. 一维状态向量每次发生的变化是线性的，只有加和乘 2. 有某种方法使得**阶段信息**是这种“和/积变换”，即进行的运算满足结合律 3. 一维状态向量变化次数很长但本身不大（一次转移的时间可以接受） **最重要的条件是，要满足结合律，这样我们对状态向量造成的更改才是可以累加的，这也是我们优化的原理** ## 5 高斯消元与线性空间 高斯消元就是对于线性方程组消元解法的一种抽取概括。通过将方程组简化为系数矩阵形式，再配合初等行变换： - 用一个非0的数乘某一行 - 最后一步消元 - 把其中一行的若干倍加到另一行上 - 加减消元 - 交换两行的位置 - 维护矩阵的有序性 高斯消元就是为了构造一种情况使得每一个元都存在这样一行满足这一行这个元的系数非0而其它都是0。然后用这样的一行把其它行的这个系数全部消去。 线性空间的概念很多，向量加法和标量乘法略。 ##### 定义5.0.1 表出 线性空间是由向量组成的集合，它关于以上两个基本运算封闭。 若向量b能被若干向量 $a_1,a_2,\ldots,a_n$ 通过向量加法和标量乘法运算得出，那么就称向量b能被向量 $a_1,a_2,\ldots,a_n$ 表出。 向量 $a_1,a_2,\ldots,a_n$ 可以表出的所有向量构成一个向量空间，而以上向量称为该向量空间的生成子集。 如果在一些向量中，存在一个向量能被其他向量表出，就称这些向量线性相关，否则称它们线性无关。 定义线性无关的生成子集（或线性空间中的极大线性无关子集），被称为线性空间的基底（简称基）。一个线性空间的所有基底包含的向量数量都相同，这称为线性空间的维数。 ------------------------ 简单来说，这里面最重要的概念应该是基，基是线性空间的一个子集，并且它里面的变量不能互相表出，这些向量可以表出线性空间的其他所有向量。其内部完全精简，可以生成整个线性空间，可以作为该线性空间的代表。 对于高斯消元进行的初等行变换，其实就是把行向量执行线性空间的基本操作： - 用一个非0的数乘某一行 - 标量乘法 - 把其中一行的若干倍加到另一行上 - 向量加法 所以其不改变其能够张成的线性空间。最后高斯消元得出的“简化阶梯形矩阵”中，非0行向量的个数就是能够张成原来线性空间的一个基。 实际上，这就好像再给原来的生成子集“去重”，求出了线性空间的基。 这也告诉了我们一些东西：有的方程其实没有告诉你有用的信息，要解出n元方程至少需要这个“系数矩阵”的所有行向量（或者列向量）张成的线性空间的维数是n。运算封闭，告诉我们无论将“单位向量”怎么变化都不会创造新的信息。 请自行理解，解释这微妙的关系实在是比较困难。 ## 6 组合计数 ##### 原理6.0.1 加法原理 如果完成一件事的方法有n类，且这些方法互不重合，那么完成这件事的方法数就是这n类方法数的和。 ##### 原理6.0.2 乘法原理 如果完成一件是需要n步，其中每一个步骤都有若干不同的方法，并且这些步骤互不干扰，那么完成这件事的方法数就是这些步骤方法数的乘积。 -------------- 这两个是本单元的基础。十分简单明了，是吗？ ##### 定义6.0.1 排列数 从n个不同元素中选取m个不同元素排成一列，产生的不同排列数目为： $$ A^m_n=\frac{n!}{(n-m)!} $$ ##### 定义6.0.2 组合数 从n个不同元素中选取m个不同元素构成一个集合，产生的不同集合数目为： $$ C_n^m=\frac{n!}{m!(n-m)!} $$ ##### 推论6.0.1 组合数的性质 1. $C_n^m=C_n^{n-m}
  1. C_n^m=C_{n-1}^m+C_{n-1}^{m-1}
  2. \sum_{i=0}^nC_n^i=2^n

以上推论根据6.0.2乘法/6.0.1加法原理以及组合数的定义不难证明。

组合数与排列数包含阶乘除法，我们常常需要预处理阶乘以及阶乘的逆元来处理。

这些性质可以用于递推求组合数等。

定理6.0.1 二项式定理
(a+b)^n=\sum_{k=0}^{n}C_n^ka^kb^{n-k}

对求和运算符进行代数变化可得结论。应用数学归纳法：

  1. 证明n=1时成立

  2. 设n=m时成立，判断n=m+1时成立

代数变形过于复杂，略去。

定理6.0.2 多重集的排列组合数

多重集的排列数：

\frac{n!}{n_1!n_2!\ldots n_k!}

其中n是集合的大小，分子每一个 n_i 是指第i种元素的数量。

多重集的组合数（保证取出的数小于任何一个元素的数量）：

C_{k+r-1}^{k-1}

k是元素的种类数，r是取出的元素数量。

证明略。下面多重集的组合数是通过转化条件，将r看作物品，使用k-1个板子分这些物品得到的。

定理6.0.3 Lucas定理

如果p是质数，则对于任意的整数 1\le m\le n ，有：

C_n^m\equiv C_{n\bmod p}^{m\bmod p}\times C_{n\div p}^{m\div p}\pmod p

证明超出了讨论范围，略。

这条定理使得我们在计算模意义下的组合数时可以先模/除再乘。

定理6.0.4 Catalan数列

给定n个0与n个1，把它们按照某种顺序排成一列，满足任意前缀0的个数都不大于1的个数的排列数量是：

Cat_n=\frac{C_{2n}^{n}}{n+1}

证明略。有一些问题与卡特兰数列有关：括号序列、出栈序列、二叉树构成数量等。

7 容斥原理与莫比乌斯函数

原理7.0.1 容斥原理

如果 S_1,S_2,S_3,\ldots,S_n 是有限集合， \lvert S\rvert 表示集合的大小，那么：

\left|\bigcup_{i=1}^nS_i\right|=\sum_{i=1}^n\left|S_i\right|-\sum_{1\le i<j\le n}\left|S_i\cap S_j\right|+\ldots + (-1)^{n+1}\left|S_1\cap S_2\cap \ldots\cap S_n\right|

简单提炼一下：奇加偶减

多重集的组合数略。本质上是：

定义7.0.1 莫比乌斯函数

设正整数 N 按照算术基本定理分解质因数为 N=p_1^{c_1}p_2^{c_2}\ldots p_m^{c_m} ，那么定义函数：

\mu(N)=\begin{cases} 0 && \exists i\in[1,m],c_i>1\\ 1 && m\equiv 0\pmod 2,\forall i\in [1,m],c_i=1\\ -1 && m\equiv 1\pmod 2,\forall i\in [1,m],c_i=1 \end{cases}

称 \mu(N) 是莫比乌斯函数

这个函数反映了 N 的质因数分解情况。

如果要求大量该函数的值，同 \varphi 一样，运用筛法即可。

8 概率与数学期望

定义略。

通俗地说：

推论8.0.1 数学期望是线性函数

满足 E(aX+bY)=a\times E(X)+b\times E(Y)

这一性质是我们可以对数学期望递推求解的根本依据。

9 0/1分数规划

0/1分数规划问题描述略。

之前我们在图论总结里面说：

其实0/1分数规划可以这样想，就是设一个mid，然后建立一个不等式mid\leq or \geq \cfrac{\sum_{i-1}^{t}a[i]}{\sum_{i-1}^{t}b[i]}

然后再化成大于小于0的形式就行了

这样逆向想比正着要好很多。

10 博弈论初步

NIM博弈以及相关概念略，其很想动态规划以及搜索我们提到的状态空间。只不过把状态换成了“局面”。

考虑这种问题一般都考虑无失误的理想情况。

定理10.0.1 NIM博弈的胜负

NIM博弈先手必胜，当且仅当每堆石子的数量之异或和非0。

考虑数学归纳法：

  1. 对于所有物品都取光，显然是必败局面

  2. 证明所有满足定理的情况都可以使得对手面对石子异或起来等于0的局面

  3. 证明所有不满足定理的情况在取一步都必然使得石子再异或起来不等于0

  4. 反推

定义10.0.1 公平组合游戏ICG

若一个游戏满足：

  1. 由两名玩家交替行动

  2. 每一次可以执行的合法操作与轮到哪个玩家无关

  3. 不能行动的玩家判负

公平组合游戏的进程可以转化为一张DAG（有向图游戏），其中入度为0的点（起始状态）只有一个。

定义10.0.2 Mex运算

定义S是一个非负整数集合，那么 \operatorname {mex}(S) 表示求出不属于 S 的最小非负整数

定义10.0.3 SG函数

对于每一个局面 x ， \operatorname {SG}(x) 的值就是其后继节点 \operatorname {SG} 函数值的 \operatorname {mex} 运算结果。特别地，定义有向图游戏 G 的 SG 函数值是其起点的 SG 函数值。

若有 m 个有向图游戏，定义一个有向图游戏 G 其规则是每一步任选一个有向图游戏行动一步，则 \operatorname {SG}(G) 就是这 m 个有向图游戏的 SG 函数值的异或和。

定理10.0.2

有向图游戏的某个局面必胜，当且仅当该局面的SG函数值大于0。

有向图游戏的某个局面必败，当前仅当该局面的SG函数值小于0。

证明类似NIM游戏，略。求解此类问题，要找准起始状态、胜利状态、失败状态，然后倒推，适当时还要考虑转换一个游戏为多个游戏的和。

11 例题

方法本来没什么好说的。但是分解阶乘的质因数在题目要求对组合数进行高精度运算的时候十分实用，避免了高精度除法。

首先 k\bmod i=k-\lfloor \frac{k}{i}\rfloor\times i 执行第一步转化。当你的式子里出现取模的时候这样的转换操作很常见。

然后这个过程就神奇了，恐怕lyd是没想着让你看懂。

这个规律如果要找，就只能先手模，然后猜，笔者也不知道lyd怎么设出 g(x) 的。

这道题的模数不一定两两互质，使用EXCRT。不再赘述。

考虑把矩阵变成向量，并且移动数、加、取走都可以用矩阵加与乘表示。然后对于每一秒构造转移矩阵。

这里有一个技巧：我们加了一行用来存储常数1，来作为石头来源，当需要常数加的时候可以考虑。

这道题对高斯消元的使用范围进行了扩展。

异或运算当然也能类似的将行向量张成“异或空间”，该空间对于向量异或和运算封闭。这是他可以使用高斯消元的原因。

这道题有比较明显的二分单调性，那么我们要解决的问题就是求一段区间之内有多少含平方因子。

为了避免重复统计：例如避免含4的平方被含16平方的再统计一次，这就自然引出容斥原理了。

然后找规律，发现容斥中数x的系数正是 \mu(x)

期望DP，通常都要从终止状态开始倒推。因为如果要正着推是需要算出从起始到终止的概率的，不方便。如果起始状态唯一，那么它的概率当然是1，这就不用计算了。

这道题的每一个操作将一个有向图游戏切成更多独立的有向图游戏。但是这道题有一个特殊的地方，就是不能行动的局面要判胜，这不符合ICG的定义。

我们通过几个无法行动状态之前的必败局面作为终止状态，将这个问题进行了转换。

这道题并不是数学。

但是实际上这道题的思想与线性空间的基十分相似。

把每一个移动方式看成二维向量，那么题目就是求这些向量可不可以生成整个二维线性空间。

所以有可能亦可以用高斯消元，看看消完之后会不会剩下一个(1,0)/(0,1)