记录许多数学方面的小东西
AC_notonlyAC
·
·
算法·理论
Tips：希腊字母读法
$\mu$ 为 `mu`
$\lambda$ 为 `lambda`
$\sigma$ 为 `sigma`
$\epsilon$ 为 `epsilon`
$\omega$ 为 `omega`
# 裴蜀定理
- 存在整数$x,y$，使得$ax+by=\gcd(a,b)$ 成立。
- 二元一次不定方程：
$$$ a_1x_1 + a_2x_2 = b.$$$
裴蜀定理指出，该方程有解，当且仅当
$$$\gcd(a_1,a_2) \mid b.$$$
# 扩展欧几里得算法
### 求法
找到该方程的一组解：
$$$ ax+by=c $$$
不难联想到裴蜀定理。首先递归求 $\gcd$ ，一般的代码写法使最终答案通常是 $\begin{cases}x=1 \\ y=0 \\\end{cases} .$ 倒推。倒推过程中发现现在已知 $ax'+ (a\bmod b) \ y' =\gcd(b,a\bmod b)$ 是一组可行解，求 $ ax+by=\gcd(a,b) $ 的一组可行解。结合二式可得
$$$ax+by=ax'+ (a\bmod b) \ y'$$$
将 $ a\bmod b=a-b \times \lfloor \dfrac{a}{b} \rfloor $ 带入，整理得
$$$ay'+b\times(x'-\lfloor \dfrac{a}{b} \rfloor \times y') = \gcd(a,b)$$$
因此，$\begin{cases}x=y' \\ y=x'-\lfloor \dfrac{a}{b} \rfloor \times y' \\\end{cases} $ 是原式的一组可行解。
### 扩展欧几里得算法求逆元
乘法逆元是数论中的一个重要概念。给定整数 $a$ 和模数 $m$，如果存在整数 $x$ 使得 $ax≡1 ( \bmod \ m )$ ，则称 $x$ 是 $a$ 在模 $m$ 下的乘法逆元，记作 $a^{−1}$ 。
使用欧几里得算法求 $\gcd(a,m)$。如果 $\gcd(a,m)=1$，则 $a$ 在模 $m$ 下没有逆元。如果 $\gcd(a,m)=1$，则通过扩展欧几里得算法求出 $x$ 和 $y$，使得：
$$$ax+my=1$$$
此时，$x$ 就是 $a$ 在模 $m$ 下的逆元。
# 费马小定理
### 定义
- 设 $p$ 是素数。对于任意整数 $a$ 且 $p\nmid a$，都成立$a^{p-1}\equiv 1\pmod p$.
- 设 $p$ 是素数。对于任意整数 $a$，都成立 $a^{p}\equiv a\pmod p$.
### 费马求逆元
由费马小定理可得，
$$$a \times a^{p-2} \equiv 1\pmod p$$$
可得 $a^{p-2}$ 是 $a$ 在 $\bmod \ p$ 意义下的逆元。
# CRT
解决问题类似于扩展欧几里得算法的推广。给出下面一组同余方程的通解。
$$$\begin{cases}x\equiv a_1 \ (\bmod \ p_1)\\x\equiv a_2 \ (\bmod \ p_2)\\.\ . \ .\\x\equiv a_n \ (\bmod \ p_n)\\\end{cases}$$$
其中，模数满足 $\forall \ 1\le i,j \le n, \ p_i \perp p_j$.
### 求法
将原方程组拆成 $n$ 个方程组，其中第 $i$ 个方程组中除第 $i$ 个方程形如 $x \equiv a_i (\bmod \ p_i)$ 外其他方程均变为 $x \equiv 0 \ (\bmod \ p_j)$，即 $p_j \mid x$ ，此时我们只需要将这 $n$ 个方程组解出来，所有方程组的解进行求和即可。进一步地，将第 $i$ 个方程变为 $x \equiv 1 \ (\bmod \ p_i)$，此时求出来的答案需要再乘 $a_i$ 。
现在，第 $i$ 个方程组变成了这样：
$$$\begin{cases}x_i\equiv 0 \ (\bmod \ p_1)\\x_i\equiv 0 \ (\bmod \ p_2)\\.\ . \ .\\x_i\equiv 1 \ (\bmod \ p_i) \\.\ . \ .\\x_i\equiv 0 \ (\bmod \ p_n)\\\end{cases}$$$
我们发现，除第 $i$ 个方程外，其余方程组成的方程组的通解很好求，即除 $p_i$ 外的所有模数积的倍数。设除 $p_i$ 外的所有模数的积为 $P_i$ ，则这个通解 $x_i$ 为 $P_i \times k_i$ ，其中 $k_i$ 即为倍数。将解带入第 $i$ 个方程可得
$$$ P_i \times k_i \equiv 1 \ (\bmod \ p_i) $$$
发现 $k_i$ 是 $P_i \bmod p_i$ 的逆元。求解即可。
最终答案为 $\sum_{i = 1}^{n} P_i \times k_i \times a_i.
欧拉函数
定义
### 性质
- 对于素数 $p$ ，有 $\varphi(p)=p-1
a^k \equiv \begin{cases}a^{k \bmod \varphi(m)}, &\gcd(a,m) = 1, \\a^k, &\gcd(a,m)\ne 1, k < \varphi(m), \\a^{(k \bmod \varphi(m)) + \varphi(m)}, &\gcd(a,m)\ne 1, k \ge \varphi(m).\end{cases} \pmod m
lucas 定理
对于素数 p，有
\binom{n}{k}\equiv \binom{\lfloor n/p\rfloor}{\lfloor k/p\rfloor}\binom{n\bmod p}{k\bmod p}\pmod p.
一些小而实用的积性函数
-
因数个数函数 d(u).（ 含 1 ）
-
因数和函数 \sigma(u).（ 含 1 ）
-
常函数 1(u) 或 l(u). 对于任意一个 n，都有 1(n)=1.
-
恒等函数 id(u). 对于任意一个 n，都有 id(n)=n.
-
单位元 \epsilon(u). \ \epsilon(u)=[ u=1 ].
莫比乌斯
莫比乌斯函数（Möbius 函数）定义为
\mu(n)=\begin{cases}1,&n=1,\\0,&n\text{ is divisible by a square }>1,\\(-1)^k,&n\text{ is the product of }k\text{ distinct primes}.\\\end{cases}
IN CHINESE:
\mu(n)=\begin{cases}1,&n=1,\\0,&n\text{ 有平方因子},\\(-1)^k,&n\text{ 无平方因子， $k$ 为 $n$ 的质因子个数}.\\\end{cases}
莫比乌斯函数有个性质：
\sum_{d \mid n} \mu (d) = [n=1]
狄利克雷卷积
定义
狄利克雷卷积相当于两个数论函数的一种运算。两个数论函数的狄利克雷卷积仍然是一个数论函数，定义如下：
(f * g) ( n ) = \sum_{d \mid n} f(d) \times g(\frac{n}{d}) , \forall n
很明显，这与普通的函数乘法不一样，函数的点乘是这样：
(f g) (n) = f(n) g(n) , \forall n
性质
作为一种运算，它有很多良好的性质：
:::info[群]
群是指一个集合 G ，其中所有元素关于某种二元运算（这里记为 \bigoplus ）有以下性质：
-
封闭性。\forall x,y \in G , \ x \bigoplus y \in G.
-
结合律。\forall x,y,z \in G , \ (x \bigoplus y)\bigoplus z = x \bigoplus (y\bigoplus z).
-
存在单位元。\exist \epsilon \in G , 使得 \forall y \in G , \epsilon \bigoplus y=y.
-
存在逆元。\forall x \in G , 都 \exist y \in G 使得 x \bigoplus y = \epsilon. 这里的 \epsilon 为单位元。
群在数学中很常见。如 \Z 关于加法构成一个群，\R^* 关于乘法构成一个群等。
:::
常见积性函数进行狄利克雷卷积
莫比乌斯反演
因数形式：
f(n)=\sum_{d \mid n} g(d) \iff g(n)= \sum_{d \mid n} f(d) \mu(\frac{n}{d})
其实利用了 \mu 和 1 互为彼此的逆元的性质。
倍数形式：
f(n)=\sum_{n \mid d} g(d) \iff g(n)= \sum_{n \mid d} f(d) \mu(\frac{d}{n})
整除分块
在做题时最后往往要求 \sum_{i=1}^n \lfloor \dfrac{n}{i} \rfloor 这样一个东西。
很显然做到 \operatorname{O} (n) 是容易的，但是我们有更好的做法。
我们发现其实对于每个不同的 \lfloor \dfrac{n}{i} \rfloor ，它们实际上在计算中会出现多次。最后一个出现的位置是 \lfloor \dfrac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor. 只会有 \operatorname{O} (\sqrt{n}) 个不同的数，因此复杂度可以做到 \operatorname{O} (\sqrt{n}).
多项式
定义与表示
一个多项式 f(x) ，他的一般形式为：
f(x)=a_0+a_1 \times x+a_2 \times x^2+a_3 \times x^3 + \ . \ . \ . \ + a_n \times x^n
平面上 $n+1$ 个点确定一个 $n$ 次多项式，这个称为多项式的**点值表示**。
一个多项式还可以用**下降幂**来表示：
$$$f(x)=b_0+b_1 \times x+b_2 \times x^{\underline{2}}+b_3 \times x^{\underline{3}} + \ . \ . \ . \ + b_n \times x^{\underline{n}} $$$
:::info[下降幂]
下降幂，表示为 $x^{\underline{n}}$ ，其含义为 $x \times (x-1) \times (x-2) \times . \ . \ . \times (x-n+1)$ 。它与 $\dbinom{x}{n} \times n !$ 等价。
:::
### 运算
多项式有多种运算。二元运算有加法、减法、乘法，一元运算有数乘、导数、积分、有限微积分（前缀和与差分）。
其中：
- 多项式之间的加法、减法，以及多项式的导数、微积分适合用一般形式处理。
- 多项式之间的乘法适合用点值形式处理，即两个多项式取相同的 $x$ ，将所得的结果乘起来。
- 多项式前缀和与差分适合用下降幂形式处理。
# 拉格朗日插值
Lagrange 插值的形式为：
$$$f(x)=\sum_{i=1}^ny_i\cdot\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j}$$$