数学 总结

数学

---

数学 总结

初等数论

欧拉筛法（线性筛质数）

欧拉筛法中的每个合数都只会被其最小的质因子（也可以说是最大的因子）筛去，所以复杂度是 $\mathcal O(n)$ 的。

过程大概就是枚举那每一个最大的因子与最小的质因子，需要注意的是如果那个最小的质因子是另一个枚举的因子的质因数，那么后面的质因子就应不再枚举，这里令素数表为 $Prime$。

如果 $Prime_i | x$，那么 $Prime_{i+1} \cdot x$ 的最小质因子就是 $Prime_i$ ，$Prime_{i+2}, Prime_{i+3}$ 及后面的质数也一样，如果这时不退出的话一些数就会被重复筛去。

算术基本定理

任意一个大于 $1$ 的整数 $n$ 都能分解为几个质数之积，就像下面这个形式

$$n = \prod a_{k}^{b_{k}}$$
因为这个分解是惟一的，所以这个定理又叫”唯一分解定理“。

为什么是唯一的呢？因为如果任意一个 $b_k$ 减一，那就需要再补一个 $a_k$ 的因子，然而 $\{a\}$ 都是质数，所以分解唯一。

其实就是分解质因数。但是这个暴力枚举的复杂度是 $\mathcal O(\sqrt n)$

之前说了线性筛能够保证用每一个数最小的质因子来筛去某一个数，其实就是可以 $\mathcal O(n)$ 求出每个数最小的质因子，那么就可以用来加速多个数质因数分解。前几天打 cf 的时候遇到了这样的一道题。。。

一些算术基本定理的推论：

• $n$ 的正约数个数为 $\prod (b_k+1)$
• $n$ 的所有正约数之和为 $\prod(\sum_{i=0}^{b_k} a_k^i)$

Codeforces 1047C

裴蜀定理（Bézout's identity）

对于不定方程 $ax+by=c$，只有当 $gcd(a,b) \mid c$ 时才有整数解。

欧几里得算法

$$gcd(a,b)=gcd(b,a \bmod b)$$

这个没啥好讲的，但我还是要证明一下。

令 $\lfloor \frac{a}{b} \rfloor$ 为 $p$，$a \bmod b$ 为 $r$，$a=pb+r$。对于 $a, b$ 任意公因数 $d$，$d | a,d | pb$， 那么 $d|(a-pb)$，也就是 $d|(a \bmod b)$，所以 $a,b$ 的公因数集合与 $b, a \bmod b$ 的公因数集合相同。

扩展欧几里得

根据前面的裴蜀定理可知，不定方程 $ax+by=c$，只有当 $gcd(a,b) \mid c$ 时才有整数解 。那么我们只要求出一组 $ax+by=gcd(a,b)$ 的特解，就可以求出一组原方程的特解。

那么该怎么求解呢？

扩展欧几里得可以解决这个问题，求出一组 $|x|+|y|$ 最小的解。

推导过程：

​ 我们已知 $gcd(a,b)=gcd(b, a \bmod b)$，那么 $ax+by=gcd(a,b)=bx'+(a \bmod b)y'$。化简得 $ax+by=ay'+b(x- \lfloor \frac{a}{b} \rfloor y')$。因为只要求一组解，我们可以直接这样子：

$$\begin{cases} x = y' \\ y = x - \lfloor \frac{a}{b} \rfloor y' \end{cases}$$
那么直接递归求解就行了，至于为什么能求出一组 $|x|+|y|$ 最小的解，我也很迷茫

更相减损术

这个算法来自《九章算数》，它原本是为约分而设计的，但适用于任何求最大公因数的问题。

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

请自行翻译

大概就是有两个式子

$$gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)$$

这里默认 $a \geq b$

因为对于 $a,b$ 的任意公因数 $d$，$d|(a-b)$，所以上式得证。

还有 $gcd(a,b)*2=gcd(2a,2b)$，这个式子显然成立。

在高精度下求 gcd 可考虑用更相减损术代替欧几里得。

Stein 算法

其实更相减损术很像这个 Stein 算法

众所周知，欧几里得算法求 gcd 很♂快

但是在算大整数的时候，需要试商，就会变慢。Stein 算法很好的解决了这个问题。

如果 $a,b$ 中有一个奇数，那我们就可以将另一个数中的质因子 $2$ 全部约去，因为这个时候两数的 gcd 不可能是 $2$ 的倍数。

剩下的就和更相减损术差不多。

欧拉函数

$\varphi(n)$ 欧拉函数等于 $\sum_{i=1}^n [gcd(n,i)=1]$。也就是与 $n$ 互质并小于 $n$ 的数的个数。

算数基本定理有 $n = \prod a_{k}^{b_{k}}$，那么 $\varphi(n) = n*\prod_{质数k|n} (1-\frac{1}{k})$。

大概证明一下
$n$ 的质因子 $p$ 会在与 $n$ 互质的数集合中筛去 $\frac{n}{p}$ 个数，质因子 $r$ 同理。因为一个数的质因子不会大于 $\sqrt{n}$，所以 $p*r$ 一定小于 $n$，那么在 $1-n$ 中，$pr$ 的倍数就会被筛去两次，所以容斥一下，答案加上 $\frac{n}{pr}$。
$n - \frac{n}{p} - \frac{n}{r} + \frac{n}{pr}$ 化简可得 $n(1-\frac{1}{p})(1-\frac{1}{r})$。

分解 $n$ 的质因数时可以求出 $\varphi(n)$。

51NOD1040 最大公约数之和

然后有些性质

• $1$ 到 $n$ 中与 $n$ 互质的数的和为 $\frac{n}{2} \cdot \varphi(n)$。
• 若 $a,b$ 互质，则 $\varphi(a,b)=\varphi(a) \varphi(b)$。
• 唯一分解定理有 $n=\prod a_k^{b_k}$，那么 $\varphi(n)=\prod \varphi(a_k^{b_k})$ 。
• 当 $p$ 是质数时，如果 $p \mid i$，$\varphi(pi)=p \cdot \varphi(i)$，否则 $\varphi(pi)=(p-1) \cdot \varphi(i)$。

那么就可以线性筛出 $1$ 到 $n$ 内的 $\varphi(i)$。

欧拉定理

如果正整数 $a,n$ 互质，就有 $a^{\varphi(n)}≡1 \pmod n$。

还是如果 $a,n$ 互质，$a^n≡a^{b\ \ mod \ \ \varphi(n)}\pmod n$，那么这个就可以在指数很大的时候用来降幂。

费马小定理

若 $p$ 为素数，有 $a^p≡a\pmod p$。

其实就是欧拉定理中的 $b$ 为素数时两边乘个 $a$。

乘法逆元

当 $b,p$ 互质时，有一个正整数 $x$ 满足 $ax≡\frac{a}{b} \pmod p$。称这个数 $x$ 为 $b$ 在模 $p$ 意义下的乘法逆元。化简得 $xb≡ 1 \pmod p$。想一想，前面欧拉定理是不是讲过　“如果正整数 $a,n$ 互质，就有 $a^{\varphi(n)}≡1 \pmod n$。”？那么 $b^{\varphi(p)-1} \pmod p$ 就是 $b$ 的乘法逆元，直接上快速幂。当然也可以用扩展欧几里得来求方程 $xb-py=1$ 的解。

但是还有一种线性递推逆元的办法。

现在要求 $i$ 的逆元 $i^-1 \pmod p$，设 $k = \lfloor \frac{p}{i} \rfloor,j = p \mod i$。$ki+j=p$。

那么有$ki+j≡0 \pmod p$，两边乘上 $i^{-1} j^{-1}$ 得 $kj^{-1}+i^{-1}≡0 \pmod p$。最后有 $i^{-1}≡-kj^{-1} \pmod p$。也就是 $i^{-1}≡-\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p$。

但是这样可能求出来的逆元是个负数，所以加上个 $p \cdot (p \bmod i)^{-1}$。也就是 $i^{i-1}≡p-\lfloor \frac{p}{i} \rfloor \cdot (p \bmod i)^{-1} \pmod p$。那么这样子就可以线性递推出 $1$ 到 $n$ 范围内模 $p$ 意义下的逆元了。

然后因为同余的传递性，$i^{-1}≡(i \bmod p)^{-1} \pmod p$。打个表以及根据上面的性质可以发现，其实在 $p \leq n$ 的时候，$1$ 到 $n$ 的逆元是有循环节的。所以在求 $i$ 的逆元的时候，可以直接先把 $i$ 模 $p$。

中国剩余定理

有同余方程组

$$\begin{cases} x≡a_1 \pmod {m_1} \\ x≡a_2 \pmod {m_2} \\ \vdots \\ x≡a_n \pmod {m_n} \\ \end{cases}$$
其中 $\{m\}$ 两两互质。

中国剩余定理，是中国古代数学家孙子智慧的结晶，用来求解如上的一元线性同余方程组。

现在令 $p$ 为 $\prod_{i=1}^n m_i$，也就是所有 $\{m\}$ 的 LCM，$g_i$ 为 $\frac{p}{m_i}$，$t_i g_i≡1 \pmod {m_i}$，也就是 $g_i$ 在模 $m_i$ 下的乘法逆元。所以 $\forall k≠i,t_i g_i a_i≡0 \pmod {m_k}$，$t_i g_i a_i ≡ a_i \pmod {m_i}$。 这时，$\sum_{i=1}^n t_i g _i a_i$ 就是方程组的一个特解。

方程的通解又可以表示为 $x+ip$。所以某些题在求最小正整数解的时候，可以直接模个 $p$，再加至非负整数。

TJOI2009 猜数字

扩展中国剩余定理

现在 $m$ 不再互质了怎么办？

扩展中国剩余定理可以很好地解决这个问题。

先令前 $k-1$ 个 $\{m\}$ 的 LCM 为 $p$，假设已经求出前 $k-1$ 个方程的一个特解 $x$，那么其通解可以表示为 $x+ip$。现在就是要求出一个 $i$，使得 $x+ip≡a_k \pmod {m_k}$，这个可以用扩展欧几里得来求解。那么新迭代下来的解为 $x+ip$，做 $n$ 次扩展欧几里得就可以求出整个方程组的一组特解，求最小正整数解的方法与上面一样。

【模板】扩展中国剩余定理

组合数学

组合数公式

• $\tbinom{n}{m}=\frac{n!}{(n-m)!m!}$ 组合数概念
• $\tbinom{n+m}{n}=\tbinom{n+m}{m}$ 非常显然
• $\tbinom{n}{m}=\tbinom{n-1}{m}+\tbinom{n-1}{m-1}$ 组合数基本的递推公式，可以发现就是杨辉三角
• $\tbinom{n}{m}=\tbinom{n}{m-1} \cdot \frac{n-m+1}{m}$ $\tbinom{n}{m}$ 与 $\tbinom{n}{m-1}$ 相除可以得出
• $\sum_{i=0}^n \tbinom{n}{i}=2^n$ $\sum_{i=0}^n \tbinom{n}{i}$ 其实就是 "从 $n$ 个不同元素中取出若干个元素" 的方案数，每个元素可选可不选，也就是 $2^n$
• 二项式定理 $(a+b)^n=\sum_{k=0}^n \tbinom{n}{k} \cdot a^k b^{b-k}$ 可用数学归纳法证明
• 从 $(0,0)$ 走到 $(n,m)$，不碰到直线 $y=x+b$ 的方案数为 $\tbinom{n+m}{n}-\tbinom{n+m}{n-b}$

斯特林数（Stirling number）

表示最后是上谷歌找到如何打 斯特林数 的正确姿势

第一类斯特林数

$n \brack m$ 表示 $n$ 个不同元素分成 $m$ 个圆排列的方案数。

有递推公式 ${n \brack m}={n-1 \brack m}*(n-1)+{n-1 \brack m-1}$。

第二类斯特林数

${n \brace m}$ 表示 $n$ 个不同元素分成 $m$ 个集合的方案数。

有递推公式 ${n \brace m}={n-1 \brace m}*m+{n-1 \brace m-1}$。

容斥原理

离散概率