数学
注意：本章属于知识点大杂烩，关于题目会新开一篇。
质数
- 不超过 \(N\) 的质数个数大约为 \(\frac{N}{\ln N}\)。
- 线性筛法，每次用最小的质因子筛质数，可以用来 \(O(n)\) 快速筛诸如欧拉函数、因子个数等。
- \(N = p_1 ^ {c_1} * ... * p_k^{c_k}\)
约数
- \(N\) 的正约数集合：\(\{p_1 ^ {b_1} * ... * p_k^{b_k}\}\)，其中 \(0\leq b_i \leq c_i\)
- \(N\) 的正约数个数：\(\prod_{i = 1}^{k}(c_i + 1)\)
- \(N\) 的正约数和：\(\prod_{i = 1}^{k}\left (\sum_{j = 0}^{c_i}(p_i) ^ j \right )\)
- \(int\) 范围内约数个数最多的数有 \(1600\) 个约数
最大公约数
- \(\forall a,b \in N\), 有 \(a \geq b, \gcd(a, b) = \gcd(b, a - b) = \gcd(a, a - b)\)
- \(\forall a,b \in N\), 有 \(\gcd(2a, 2b) = 2 \gcd(a, b)\)
- \(\forall a,b \in N, b \ne 0\), 有 \(\gcd(a, b) = \gcd(b, a \mod b)\)
整除分块
考虑对于式子 \(\sum_{i = 1}^{n} f(i)g(\lfloor \frac{n}{i} \rfloor)\)，\(\lfloor \frac{n}{i} \rfloor\) 的可能值个数在 \(\sqrt n\) 左右，每一段可能值都覆盖连续地一段 \([l, r]\)。如果我们能预处理出 \(f\) 的前缀和我们就可以通过 \((f(r) - f(l - 1)) * g(\lfloor \frac{n}{l} \rfloor)\) 来快速计算上述式子的结果。
可以证明对于某一块的左端点 \(l\)，则右端点为 $\left \lfloor \frac{n}{\left \lfloor \frac{n}{l} \right \rfloor} \right \rfloor $。
整除分块是一个非常有用的技巧。
莫比乌斯函数
定义莫比乌斯函数 $\mu(n) = \left{\begin{matrix}
1 & n = 1 \
0 & n 含有相同质因子 \
(-1)^s & s 为 n 的质因子数量
\end{matrix}\right. $
莫比乌斯函数为积性函数，则显然可以通过筛法求出莫比乌斯函数。（这里把求 \(phi\) 的过程一同写了）
mu[1] = 1, phi[1] = 1;
for (int i = 2; i <= n; i ++) {
if (!st[i]) primes[++ cnt] = i, phi[i] = i - 1, mu[i] = -1;
for (int j = 1; primes[j] <= n / i; j ++) {
int p = primes[j]; st[i * p] = 1;
if (i % p == 0) { phi[i * p] = phi[i] * p; break; }
phi[i * p] = phi[i] * (p - 1), mu[i * p] = -mu[i];
}
}
有一个性质是 \(\sum_{d | n}\mu(d) = [n = 1]\)。
积性函数
- 当 \(a, b\) 互质时，有 \(f(ab) = f(a) \times f(b)\)，则称 \(f\) 为积性函数
- 若 \(f\) 是积性函数，且 \(n = \prod_{i = 1}^{k}p_i ^ {c_i}\)，则 \(f(n) = \prod_{i = 1}^{k}f(p_i^{c_i})\)
互质与欧拉函数
-
\(\forall a, b \in N\)，若 \(gca(a, b) = 1\)，则 \(a, b\) 互质
-
\(\varphi (N) = N * \prod_{p | N}(1 - \frac{1}{p})\)，证明参考容斥原理
-
\(\forall n > 1\)，\(1 \sim n\) 中与 \(n\) 互质的数的和为 \(n \times \varphi(n) \div 2\)
-
若 \(a, b\) 互质，则 \(\varphi(a, b) = \varphi(a)\varphi(b)\)，即 \(\varphi\) 为积性函数
-
设 \(p\) 为质数，若 \(p | n\) 且 \(p^2|n\)，则 \(\varphi(n) = \varphi(\frac{n}{p}) \times p\)
-
设 \(p\) 为质数，若 \(p|n\) 且 \(p^2\nmid n\)，则 \(\varphi(n) = \varphi(\frac{n}{p}) \times (p - 1)\)
-
\(\sum_{d | n}\varphi(d) = n\)
证明(\(7\))：令 \(f(n) = \sum_{d|n} \varphi(d)\)，设 \(n, m\) 互质，则 \(f(nm) = \sum_{d | nm} \varphi(d) = \sum_{d | n}\varphi(d) \times \sum_{d | m}\varphi(d) = f(n) \times f(m)\)
又 \(f(p^k) = \sum_{d | p^k} \varphi(d) = \varphi(1) + \varphi(p) + ... + \varphi(p^k) = 1 + p - 1 + p^2 - p + ... + p^k - p^{k - 1} = p^k\)
\(\therefore f(n) = \prod_{i = 1}^{k}f(p_i^{c_i}) = \prod_{i = 1}^{k}p_i^{c_i} = n\)
同余
- 对于 \(\forall a \in [0, m - 1]\)，集合 \({a + km}(k \in Z)\) 的所有数模 \(m\) 同余，该集合称为一个模 \(m\) 的同余类，记为 \(\bar{a}\)
- 模 \(m\) 的同余类共有 \(m\) 个，分别为 \(\bar{0}, \bar{1}, ... \bar{m - 1}\)，它们构成 \(m\) 的完全剩余系。
- \(1 \sim m\) 中与 \(m\) 互质的数共有 \(\varphi(m)\) 个，它们构成 \(m\) 的简化剩余系。
- 简化剩余系关于模 \(m\) 乘法封闭（乘法封闭即 \(\forall a, b \in S\)，\(ab \in S\)）。
欧拉定理
- 若正整数 \(a, n\) 互质，则 \(a ^ {\varphi(n)} \equiv 1 \pmod{n}\)
证明：设 \(n\) 的简化剩余系为 \(\{\bar{a_1}, \bar{a_2}, ..., \bar{a_{\varphi(n)}}\}\)，对于 \(\forall a_i, a_j\)，若 \(a\times a_i \equiv a \times a_j \pmod n\)，则可推出 \(a_i \equiv a_j \pmod n\)，矛盾。
所以，当 \(a_i \ne a_j\) 时，\(\bar{aa_i}\) 与 \(\bar{aa_j}\) 代表不同的同余类。
根据上文所述的乘法封闭，\(\bar{aa_i}\) 也在简化剩余系中，所以 \(\{\bar{aa_1}, \bar{aa_2}, ..., \bar{aa_{\varphi(n)}}\}\) 也是 \(n\) 的简化剩余系。
注意到 \(a^{\varphi(n)}\) 与 \(n\) 互质，所以 ：
$$ a^{\varphi(n)}a_1a_2...a_{\varphi(n)} \equiv (aa_1)(aa_2)...(aa_{\varphi(n)}) \equiv a_1a_2...a_{\varphi(n)} \pmod n$$
因为 \(a_1a_2...a_{\varphi(n)}\) 与 \(n\) 互质，所以 \(a^{\varphi(n)} \equiv 1 \pmod n\)
- 由欧拉定理引申出费马小定理：对于任意正整数 \(a, p\) 互质且 \(p\) 为质数，则 \(a^{p - 1} \equiv 1 \pmod p\)
证明：由欧拉定理得 \(a^{\varphi(p)} \equiv 1 \pmod p\)，又因为 \(p\) 为质数，所以 \(\varphi(p) = p - 1\)，所以 \(a^{p - 1} \equiv 1 \pmod p\)
- 费马小定理也可以写成：对于任意整数 \(a\)，若 \(p\) 是质数，有 \(a^p \equiv a \pmod p\)
- 欧拉定理的推论：若正整数 \(a, n\) 互质，则对于任意正整数 \(b\)，有 \(a^b \equiv a^{b \bmod \varphi(n)} \pmod n\)
证明：设 \(b = q \times \varphi(n) + r\)，其中 \(0 \leq r < \varphi(n)\)，即 \(r = b \bmod \varphi(n)\)
那么 \(a^b = a^{q \times \varphi(n) + r} = (a^{\varphi(n)})^q \times a^r \equiv 1^q \times a^r \equiv a^r \equiv a^{b \bmod \varphi(n)} \pmod n\)
- 由欧拉定理的推论，对于乘方算式，可以将底数对 \(p\) 取模，指数对 \(\varphi(p)\) 取模
- 当 \(a, n\) 不一定互质且 \(b > \varphi(n)\) 时，有 \(a^b \equiv a^{b \bmod \varphi(n) + \varphi(n)} \pmod n\)，可以通过寻找 \(a^b \pmod n\) 的指数循环节来证明。
拓展欧几里得
- 裴蜀定理（Bézout 定理）：对于 \(\forall a, b \in Z\)，存在一对整数 \(x, y\)，满足 \(ax + by = gcd(a, b)\)
证明：当 \(b = 0\) 时，显然有 \(x = 1, y = 0\)。
当 \(b > 0\) 时，有 \(\gcd(a, b) = \gcd(b, a \bmod b)\)。存在 \(x, y \in Z\) 使得 \(b \times x + (a \bmod b) \times y = \gcd(b, a \bmod b)\)
变型得，\(ay + b(x - \lfloor \frac{a}{b} \rfloor y)\)，令 \(x^{'} = y, y^{'} = x - \lfloor \frac{a}{b} \rfloor y\)，可得 \(ax^{'} + by^{'} = gcd(b, a \bmod b) = gcd(a, b)\)
对欧几里得算法的过程采用数学归纳法即可证明裴蜀定理。
-
设 \(d\) 为 \(\gcd(a, b)\)，根据上述过程可以求出 \(ax + by = d\) 的一组特解 \(x_0, y_0\)
-
对于方程 \(ax + by = c\)，它有解的充要条件是 \(d | c\)，满足该条件则原方程的一组特解为 \(\frac{c}{d}x_0, \frac{c}{d}y_0\)
-
由于 \(a(x + k\frac{b}{d}) + b(y - k\frac{a}{d}) = ax + by\)，所以 \(ax + by = c\) 的通解可表示为：
\[x = \frac{c}{d}x_0 + k\frac{b}{d}, y = \frac{c}{d}y_0 - k\frac{a}{d} (k \in Z) \]
int exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, x, y);
int z = x;
x = y, y = z - y * (a / b);
return d;
}
线性同余方程
长相类似 \(a \times x \equiv b \pmod m\)，其等价于 \(a\times x - b\) 为 \(m\) 的 \(-y\) 倍，于是可以得到 \(ax +ym = b\)。
根据拓展欧几里得，该方程有解当且仅当 \(\gcd(a, m) | b\)，有解时直接拓展欧几里得做即可。
乘法逆元
若整数 \(b, m\) 互质，且 \(b | a\)，则存在整数 \(x\) 满足 \(a \div b \equiv a \times x\pmod m\)，\(x\) 即为 \(b\) 的模 \(m\) 乘法逆元，记为 \(b^{-1}\pmod m\)
可以用费马小定理证明 \(x = b^{m - 2}\)，可以用于解决除法取模。
中国剩余定理
设 \(m_1, m_2, ..., m_n\) 是两两互质的整数，\(m = \prod_{i = 1}^{n}m_i\)，\(M_i = m \div m_i\)，\(t_i\) 为 \(M_it_i \equiv 1 \pmod {m_i}\) 的一个解。对于任意 \(n\) 个整数 \(a_1,a_2,...,a_n\) 组成的方程组：
有整数解 \(x = \sum_{i = 1}^{n}a_iM_it_i\)
拓展中国剩余定理
当 \(m_1, m_2, ..., m_n\) 不两两互质时，便无法使用中国剩余定理，好在我们可以借助数学归纳法求解。
设已经求出前 \(k - 1\) 个方程的一个解 \(x\)，记 \(m = \operatorname{lcm}(m_1, m_2, \cdots, m_{k - 1})\)，则前 \(k - 1\) 个方程的通解为 \(x + im(i \in Z)\)。
那么对于第 \(k\) 个方程，我们求出整数 \(t\) 使得 \(x + tm \equiv a_k \pmod{m_k}\)，变形得 \(tm \equiv a_k - x \pmod{m_k}\)，可以使用拓展欧几里得求解。
求解出 \(t\) 后，则 \(x^{'} = x + tm\) 为前 \(k\) 个方程的通解，一直做到第 \(n\) 个方程即可。
// 洛谷模板题暴 LL，遂 int128
__int128_t n, a, m, M, x;
__int128_t exgcd(__int128_t a, __int128_t b, __int128_t &x, __int128_t &y) {
if (!b) {
x = 1, y = 0;
return a;
}
__int128_t d = exgcd(b, a % b, x, y), z = x;
x = y, y = z - y * (a / b);
return d;
}
__int128_t gcd(__int128_t a, __int128_t b) {
return b ? gcd(b, a % b) : a;
}
__int128_t qmul(__int128_t a, __int128_t b, __int128_t p) {
__int128_t res = 0;
while (b) {
if (b & 1) res = (res + a) % p;
b >>= 1;
a = (a + a) % p;
}
return res;
}
int main() {
n = read();
rep(i, 1, n) {
m = read(), a = read();
if (i == 1) {
x = a, M = m;
continue;
}
__int128_t k1, k2; exgcd(M, m, k1, k2);
__int128_t d = exgcd(M, m, k1, k2), c = (a - x % m + m) % m;
if (c % d != 0) {
puts("-1");
return 0;
}
__int128_t t = k1 * c / d % m;
x = x + t * M; M = M * m / d; x = (x % M + M) % M;
}
x = (x % M + M) % M;
write(x);
return 0;
}
高次同余方程
喵？
矩阵乘法
- 对于 \(n \times m\) 矩阵 \(A, B\) 则 \(C = A \pm B \Leftrightarrow \forall i \in[1, n], j\in[1,m],C_{i, j} = A_{i, j} \pm B_{i, j}\)，即对应位置相加减
- 对于 \(n \times m\) 矩阵 \(A\) 和 \(m \times p\) 矩阵 \(B\)，\(C = A \times B\) 是 \(n \times p\) 矩阵，其中 \(\forall i \in[1, n], j\in[1, p]\)，有 \(C_{i, j} = \sum_{k = 1}^{m} A_{i, k} \times B_{k, j}\)
- 矩阵乘法满足结合律，分配律，但不满足交换律
- 矩阵乘法加速递推问题的特点：
- 可以抽象出一个长度为 \(n\) 的向量，该向量在每个单位时间发生一次变化
- 变化的形式为线性递推
- 该递推式在每个时间本身保持不变
- 向量变化时间很长，但向量长度 \(n\) 不大
- 对于矩阵乘法加速递推问题，若状态矩阵中的第 \(x\) 个数对下个状态的 \(y\) 产生影响，则把转移矩阵的 \((x, y)\) 赋值为适当的系数
- 矩阵乘法加速递推的时间复杂度是 \(O(n ^ 3logT)\)
线性空间
线性空间是一个关于向量加法与标量乘法（\(k \times a\)，其中 \(a\) 为向量，\(k\) 为标量）。
若向量 \(b\) 能够被向量 \(a_1, a_2, ..., a_k\) 通过上述操作得到，那么称向量 \(b\) 能被向量 \(a_1, a_2, ..., a_k\) 表出。
向量 \(a_1, a_2, ..., a_k\) 能表出的所有向量组成一个线性空间，\(a_1, a_2, ..., a_k\) 被称为该线性空间的生成子集。
任意选出线性空间中的若干个向量，若不存在向量能被其它向量表出，则称这些向量线性无关，否则称为线性相关。
线性空间的极大线性无关生成子集被称为线性空间的基。显然一个线性空间的所有基包含的向量个数都相等，定义为线性空间的维数。
一个例子是空间直角坐标系中的一个基就是 \(\{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}\)，维数是 \(3\)。
对于一个 \(n \times m\) 的矩阵，将它的每一行看作长度为 \(m\) 的行向量，那么这 \(n\) 个行向量能够表示出的所有向量构成一个线性空间。这个线性空间的维度称为“行秩”，同样地可以定义“列秩”。显然“行秩”等于“列秩”，合称为秩。
将 \(n \times m\) 矩阵进行高斯消元得到的简化阶梯形矩阵的所有非零行向量线性无关，且不改变原有的线性空间。所有的非零行向量即为该线性空间的基，非零行向量的个数即为矩阵的秩。
异或线性空间
定义表出为整数 \(b\) 能由整数 \(a_1, a_2, \cdots, a_k\) 经过异或得到。异或空间为 \(a_1, a_2, \cdots, a_k\) 能标出的所有整数，\(a_1, a_2, \cdots, a_k\) 即为异或空间的生成子集。
任意选出异或空间的若干个整数，如果存在一个数能被其它数表出，责成这些整数线性相关，否则线性无关。
异或空间的基就可以定义为异或空间中的一个极大线性无关子集。
将异或空间中的所有数写作 \(m\) 位二进制数，通过高斯消元，所有非 \(0\) 的整数构成异或空间的基。
设一个对于 \(a_1, a_2, \cdots, a_n\)，从中找出 \(t\) 个线性无关的整数，作为基，所以异或空间包含 \(2^t\) 个互不相等的整数，这样的到的是一个“去重异或集合”。我们如何得到不去重的呢？
从剩下的 \(n - t\) 个数中选出若干个显然有 \(2^{n - t}\) 种方法。设选取的整数异或起来为 \(x\)，把基底能表示出的 \(2^t\) 个数分别与 \(x\) 异或就能得到 \(2^t\) 个互不相等的整数（而这些数一定是基底能表示的 \(2^t\) 个数）。所以，每种取法与基底相结合恰好遍历“去重异或集合”一次。
总结一下，对于一个“去重异或集合”将它包含的 \(2^t\) 个整数各重复 \(2^{n - t}\) 次可以形成“不去重异或集合”。
和式变换
- 分配律： \(\sum_{k \in K} ca_k = c\sum_{k \in K}a_k\)
- 结合律：\(\sum_{k \in K} (a_k + b_k) = \sum_{k\in K} a_k + \sum_{k\in K} b_k\)
- 交换律：\(\sum_{k \in K}a_k = \sum_{p(k) \in K} a_{p(k)}\)
- 替换条件：\(\sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{d | \gcd(i, j)} d = \sum_{i = 1}^{n} \sum_{j = 1}^{m} \sum_{d = 1}^{n} [d | i][d|j]d\)
- 替换指标变量：\(\sum_{i = 1}^n \sum_{j = 1}^{m} [\gcd(i, j) = k] = \sum_{ik = 1}^{n} \sum_{jk = 1}^{m} [\gcd(ik, jk) = k] = \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i, j) = 1]\)
- 交换求和次序：\(\sum_{j \in J} \sum_{k \in K} a_{j, k} = \sum_{k \in K} \sum_{j \in J} a_{j, k}\)。复杂一点，有 \(\sum_{j \in J} \sum_{k \in K(j)} a_{j, k} = \sum_{k \in K'} \sum_{j \in J'(k)} a_{j, k}\)，它要求 \([j \in J][k \in K(j)] = [k \in K'][j \in J'(k)]\)
- 分离变量：\(\sum_{j \in J, k \in K}a_jb_k = (\sum_{j \in J}a_j)(\sum_{k \in K}b_k)\)
- \([k \in K] + [k \in K'] = [k \in K \cap K'] + [k \in K \cup K']\)
- \(\sum_{d | n} \mu(d) = [n = 1] \Longrightarrow \sum_{d | \gcd(i, j)} \mu(d) = [\gcd(i, j) = 1]\)
- \(\sum_{d | n}\varphi(d) = n\)
普通生成函数
定义 \(F(x) = \sum_{n}a_nx^n\)，其中 \(a\) 可以是有穷序列也可以是无穷序列。
- 加法运算：\(F(x) \pm G(x) = \sum_{n}(a_n \pm b_n)x^n\)，即 \(F(x) \pm G(x)\) 是序列 \(\langle a_n \pm b_n \rangle\) 的普通生成函数
- 乘法运算（卷积）： \(F(x)G(x) = \sum_{n}x^n\sum_{i = 0}^na_ib_{n - i}\)，即 \(F(x)G(x)\) 是序列 \(\langle \sum_{i = 0}^na_ib_{n - i} \rangle\) 的生成函数。
考虑等比数列 \(\langle p, p^2, p^3, ... \rangle\) 的生成函数为 \(\sum_{n \geq 0}p^nx^n\)，我们可以将其化为封闭形式，有：
\(F(x)px + 1 = F(x)\)，从而 \(F(x) = \frac{1}{1 - px}\)。
接着考虑斐波那契数列的生成函数 \(F(x)\)，根据递推式，可以列出关于 \(F(x)\) 的方程：
\(F(x) = xF(x) + x^2F(x) - a_0x + a_0 + a_1x\)，证明可以直接展开右式会发现这是对的。
从而我们有 \(F(x) = \frac{x}{1 - x - x^2}\)。值得注意的是这里将斐波那契数列的 \(a_0\) 定义为 \(0\)。
接着我们考虑使用部分分式分解法进一步求出斐波那契数列的通项，即构造：$ \frac{A}{1 - ax} + \frac{B}{1 - bx} = \frac{x}{1 - x - x^2} $。
解得 \(\left\{\begin{matrix} A = \frac{1}{\sqrt 5} \\ B = -\frac{1}{\sqrt 5} \\ a = \frac{1 + \sqrt 5}{2} \\ b = \frac{1 - \sqrt 5}{2} \end{matrix}\right.\)
把这些都带回去就会出现类似于等比数列求和公式 \(\sum_{n = 0}^{\infty} q^n = \frac{1}{1 - q}\) 的形式，则有：
\(\frac{x}{1 - x - x^2} = \sum_{n \ge 0}x^n\frac{1}{\sqrt 5}((\frac{1 + \sqrt 5}{2}) ^n - (\frac{1 - \sqrt 5}{2})^n)\)。
那么 \(a_n = [x^n]G(x)\)，于是我们的得出 \(a_n = \frac{1}{\sqrt 5}((\frac{1 + \sqrt 5}{2}) ^n - (\frac{1 - \sqrt 5}{2})^n)\) 。
这种方法是通用的，更详细可以看这个视频：【数列通项】秘技•生成函数法的基本步骤及其进阶结论。
当然你也可以选择直接暴力计算卷积，结合后文可能提到的多项式知识。
指数生成函数
定义形式幂级数 \(\hat{F}(x) = \sum_na_n\frac{x^n}{n!}\) 为序列 \(a\) 的指数生成函数，同时也是序列 \(\langle \frac{a_n}{n!} \rangle\) 的普通生成函数。
有卷积 \(\hat{F}(x)\hat{G}(x) = \sum_{i \geq 0}a_i\frac{x^i}{i!}\sum_{j \geq 0}b_j\frac{x_j}{j!} = \sum_{n \geq 0}x^n \sum_{i = 0}^n a_ib_{n - i}\frac{1}{i!(n - i)!} = \sum_{n \geq 0}\frac{x^n}{n!} \sum_{i = 0}^n C_{n}^{i}a_ib_{n - i}\)。
因此 \(\hat{F}(x)\hat{G}(x)\) 是序列 \(\langle \sum_{i = 0}^nC_{n}^{i}a_ib_{n - i} \rangle\) 的生成函数。
狄利克雷生成函数与狄利克雷卷积
定义数列 \(\langle a_1, a_2, ... \rangle\) 的 DGF 为 \(\tilde{F}(x) = \sum_{i = 1}^{\infty}\frac{a_i}{i^x}\)。
则乘法运算为 \(\tilde{F}(x)\tilde{G}(x) = \sum_{i = 1}^{\infty}\frac{a_i}{i^x}\sum_{j = 1}^{\infty}\frac{b_j}{j^x} = \sum_{n = 1}^{\infty}\frac{1}{n^x}\sum_{d | n}a_db_{\frac{n}{d}}\)
接下来介绍这一节的重点狄利克雷卷积。
对于两个数论函数 \(f(x)\) 和 \(g(x)\)，则它们的狄利克雷卷积的到的结果定义为：
可以发现，对于两个序列 \(f, g\)，其狄利克雷生成函数之积，对应的是两者狄利克雷卷积的狄利克雷生成函数。
然后是狄利克雷卷积的一些性质：
- \(f * g = g * f\)（交换律）
- \((f * g) * h = f * (g * h)\) （结合律）
- \((f + g) * h = f * h + g * h\)（分配律）
- \(f = g \Longleftrightarrow f * h = g * h\)，其中数论函数 \(h(x)\) 满足 \(h(1) \ne 0\)（等式的性质）
接下来先定义一些函数：
- 单位函数：\(\varepsilon(n) = [n = 1]\)
- 常数函数：\(1(n) = 1\)
- 恒等函数：\(id(n) = n\)
- 幂函数：\(Id_k(n) = n^k\)
- 整除函数：\(\sigma_k(n) = \sum_{d | n}d^k\)
- 欧拉函数 \(\varphi\)，莫比乌斯函数 \(\mu\)（见上文）
接着定义数论函数 \(f(x) \ne 0\) 的逆元为满足 \(f * g = \varepsilon\) 的数论函数 \(g\)，其中 \(g = f^{-1}\)。
那么有：
- \(\sum_{d|n}\mu(d) = [n = 1] \Leftrightarrow \mu * 1 = \varepsilon\)
- \(\sum_{d | n}\varphi(d) = n \Leftrightarrow \varphi * 1 = id\)
- \(\sum_{d | n}\mu(d)\frac{n}{d} = \varphi(n) \Leftrightarrow \mu * id = \varphi\)，证明考虑容斥原理
- \(f * 1 \ne f\)
- \(Id_k * 1 = \sigma_k\)
- \(\varphi * 1 = Id\)
- \(f^{-1}(n) = -\frac{\sum_{d|n, d > 1}f(d)f^{-1}(\frac{n}{d})}{f(1)}\)
证明：
\[(f * f^{-1})(n) = \sum_{d | n}f(d)f^{-1}(\frac{n}{d}) = f(1)g(n) + \sum_{d | n, d > 1}f(d)g(\frac{n}{d}) = \varepsilon(n) = 0 \]
然后移项即可得到答案。
重要结论：
- 两个积性函数的狄利克雷卷积也是积性函数。
证明：
设两个积性函数为 \(f(x), g(x)\)，记 \(h = f * g\)，令 \(gcd(a, b) = 1\)，则
\(h(a) = (f * g)(a) = \sum_{d | a}f(d)g(\frac{a}{d}), h(b) = (f * g)(b) = \sum_{d | b}f(d)g(\frac{b}{d})\)
\(h(a)h(b) = \sum_{d_1 | a}f(d_1)g(\frac{a}{d_1})\sum_{d_2 | b}f(d_2)g(\frac{b}{d_2}) = \sum_{d_1|a}\sum_{d_2|b}f(d_1d_2)g(\frac{ab}{d_1d_2}) = \sum_{d|ab}f(d)g(\frac{ab}{d}) = h(ab)\)
- 积性函数的逆元也是积性函数，证明考虑归纳，太长不想写。
综合以上可以说明数论函数的积性在狄利克雷生成函数中的对应具有封闭形式。
莫比乌斯反演
对于积性函数 \(f(n)\) 和 \(g(n)\)，有 \(f(n) = \sum_{d | n}g(d) \Leftrightarrow g(n) = \sum_{d | n}\mu(d)f(\frac{n}{d})\)。
证明（只证明左推右，右推左证法类似）：
法一：证明左推右，即证明 \(g * 1 = f\) 可以推出 \(g = \mu * f\)。再根据狄利克雷卷积中提到的 \(\mu * 1 = \varepsilon\) 我们可以得到 \(\mu * f = \mu * g * 1 = \mu * 1 * g = \varepsilon * g = g\)。
法二（大力推式子）：
\[ \begin{align} \sum_{d | n}\mu(d)f(\frac{n}{d}) &= \sum_{d | n}\mu(d) \sum_{p | \frac{n}{d}}g(p) \\ & = \sum_{d | n}\sum_{p | \frac{n}{d}}\mu(d)g(p) \\ & = \sum_{p | n}g(p)\sum_{d | \frac{n}{p}} \mu(d) \\ & = \sum_{p | n}g(p) [\frac{n}{p} = 1] \\ & = g(n) \end{align} \]
杜教筛
杜教筛可以快速计算 \(\sum_{i = 1}^{n}f(i)\)，其中 \(f\) 为数论函数。
注意到（雾）：
所以如果我们能够构造出 \(g\) 使得可以快速计算 \(\sum_{i = 1}^n(f * g)(i)\) 和 \(g\) 的前缀和，我们就可以直接对后面那部分数论分块。可以证明如果加上记忆化的话，时间复杂度是 \(O(n ^ {\frac{2}{3}})\)。
接下来说说具体求法，以求莫比乌斯函数前缀和和欧拉函数前缀和为例。
莫比乌斯函数前缀和：
令 \(g = 1\)，则 \(S(n) = \sum_{i = 1}^n \varepsilon(i) - \sum_{i = 2}^n S(\lfloor \frac{n}{i} \rfloor) = 1 - \sum_{i = 2}^n S(\lfloor \frac{n}{i} \rfloor)\)。
结束了。
欧拉函数前缀和：
还是令 \(g = 1\)，则 \(S(n) = \sum_{i = 1}^n \operatorname{id}(i) - \sum_{i = 2}^n S(\lfloor \frac{n}{i} \rfloor) = \frac{n(n + 1)}{2} - \sum_{i = 2}^n S(\lfloor \frac{n}{i} \rfloor)\)
2025.5.10 先写到这www喵
浙公网安备 33010602011771号