个人赶脚这个东西非常好玩。
决定安利给朋友所以有了这篇笔记。
数论函数
在数论上，数论函数指定义域为正整数、值域为实/复数的函数。
通俗地讲，我们 OI 接触到的大部分函数都是数论函数，比如： - 元函数 \(\epsilon(n) = [n = 1]\) - 欧拉函数 \(\varphi(n) = \sum\limits_{i = 1}^{n - 1} [\gcd(n,i) = 1]\) - 约数个数函数 \(d(n) = \sum\limits_{i | n} 1\) - 约数和函数 \(\sigma(n) = \sum\limits_{i | n} i\)
积性函数
对于一个数论函数 \(f\)，若对于所有 \(\gcd(i,j) = 1\) 的 \(i,j\)，都有 \(f(ij) = f(i) f(j)\)，则称函数 \(f\) 是积性函数。
特别地，如果对于所有没有限制的 \(i,j\) 上式仍成立，则称该函数是完全积性函数。
狄利克雷卷积
记两个数论函数 \(f,g\) 的狄利克雷卷积为 \(f * g\)。
且 \((f * g)(n) = \sum\limits_{d | n} f(d) g(\dfrac n d)\)。
显然狄利克雷卷积具有交换律与结合律。
莫比乌斯函数
把正整数 \(n\) 分解为质因数相乘的形式 \(n = \sum\limits_{i = 1}^m {p_i}^{c_i}\)，有
\[\mu(n) = \begin{cases} 1, & n = 1 \\ 0, & \exists i \in [1,m],c_i > 1 \\ (-1)^m, & \forall i \in [1,m],c_i = 1 \end{cases}\]
显然莫比乌斯函数也是积性函数。
如果要求 \(\mu(n)\)，分解质因数即可。
如果要求 \(\mu(1) \sim \mu(n)\)，可以线性筛。
伪代码： 1
2
3
4
5
6
7
8
9
10
11getMu(n)
mu[1] = 1
for i in [2,n]
if vis[i] == 0
prime[++cnt] = i
mu[i] = -1
for j in [1,cnt] and i * prime[j] <= n
vis[i * prime[j]] = 1
if i mod prime[j] == 0
break
mu[i * prime[j]] = -mu[i]
有一个比较显然的性质：\(\sum\limits_{d | n} \mu(d) = [n = 1]\) 即 \(\mu * \textbf 1 = \epsilon\)。
证明：
首先，显然 \(\mu * \textbf 1\) 也是积性函数。
有 \((\mu * \textbf 1)(1) = 1\)。
然后考虑一个质数 \(p\)， \[(\mu * \textbf 1)(p^k) = \mu(1) + \mu(p) + \mu(p^2) + \dots + \mu(p^k) = 1 - 1 + 0 + \dots + 0 = 0\]
考虑合数 \(x,x > 1\)，将它分解为质因子相乘的形式 \(x = \prod\limits_{i = 1}^m {p_i}^{c_i}\)。
有 \((\mu * \textbf 1)(x) = \prod\limits_{i = 1}^m (\mu * \textbf 1)({p_i}^{c_i}) = 0\)。
证毕。
然后有莫比乌斯反演公式：
如果有数论函数 \(f\) 和 \(F\)，满足 \(F(n) = \sum\limits_{d | n} f(d)\)，有 \(f(n) = \sum\limits_{d | n} F(d) \mu(\dfrac n d)\)。
证明：
我们让 \(F(n) = \sum\limits_{d | n} f(d)\) 这个式子等号两边都卷上 \(\mu\)，即 \(F * \mu = f * \textbf 1 * \mu\)。
由于狄利克雷卷积有交换与结合律，所以 \(f * \textbf 1 * \mu = f * \epsilon = f\)。
所以 \(f = F * \mu\)。
这个玩意有一个更为常用的形式：若 \(F(n) = \sum\limits_{n | d} f(d)\)，那么 \(f(n) = \sum\limits_{n | d} F(d) \mu(\dfrac d n)\)。
其实莫比乌斯函数是基于容斥原理的。
例题 - Zap
给定 \(n,m,k\)，求 \(\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i,j) = k]\)。
多组询问。
设 \(f(x) = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i,j) = x],F(x) = \sum\limits_{x | d} f(d) = \lfloor \dfrac n x \rfloor \lfloor \dfrac m x \rfloor\)。
于是 \(f(x) = \sum\limits_{x | d} \mu(\dfrac d x) \lfloor \dfrac n d \rfloor \lfloor \dfrac m d \rfloor\)。
考虑把枚举的东西换成 \(\dfrac d x\)，有 \(f(x) = \sum\limits_{xi \le \min(n,m)} \mu(i) \lfloor \dfrac n {xi} \rfloor \lfloor \dfrac m {xi} \rfloor\)。
但是这样还没完，我们仍然没法直接做。
换个角度思考，\(\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\gcd(i,j) = k]\) 相当于 \(\sum\limits_{ki \le n} \sum\limits_{kj \le m} [\gcd(i,j) = 1]\)。
于是原式变为 \(\sum\limits_{i = 1}^{\min(n,m)} \mu(i) \lfloor \dfrac {\lfloor \frac n k \rfloor} i \rfloor \lfloor \dfrac {\lfloor \frac m k \rfloor} i \rfloor\)。
运用数论分块即可解决。