数论函数
ni_ju_ge
·
2026-01-03 10:21:20
·
算法·理论
前言
没有放代码。
你需要确保你学会了一些基础的数论知识，如线性筛、唯一分解定理。
::::info[一些定义和声明]{open}
积性函数
若函数 f(x) 满足对于 互质 的 a,b ，有 f(ab)=f(a)f(b) ，则 f(x) 为积性函数。
若 任意 的 a,b 均满足 f(ab)=f(a)f(b) ，则 f(x) 为完全积性函数。
对于任何的积性函数 f(x) 都有 f(1)=1 ，易证。
加性函数
若函数 f(x) 满足对于 互质 的 a,b ，有 f(ab)=f(a)+f(b) ，则 f(x) 为加性函数。
若 任意 的 a,b 均满足 f(ab)=f(a)+f(b) ，则 f(x) 为完全加性函数。
对于任何的加性函数 f(x) 都有 f(1)=0 ，易证。
等价性
若 f(x) 相当于 g(x) ，则可以记 f(x)\Leftrightarrow g(x) ，表示 f(x) 与 g(x) 等价。
卷积
两个函数的卷积记为 (f\ast g)(x) ，若是函数 f(x) 自卷积，也可记为 (f\ast f)(x)=f^2(x)
符号
为书写方便，记 a/b=\left\lfloor\dfrac{a}{b}\right\rfloor 。
::::
欧拉函数
欧拉函数即 \varphi(n) ，被定义为 1\sim n 中与 n 互质的数的个数。
特性：\
1.若 p 是质数，则 \varphi(p)=p-1 \
2.若 p 是质数，则 \varphi(p^k)=p^{k-1}\varphi(p) （证明：由于 p 是质数，则 1\sim p-1,p+1\sim 2p-1,\dots,p^k-p\sim p^{k}-1 均与 p 互质，共有 p^{k-1} 节长度为 \varphi(p) 的区间，故 \varphi(p^k)=p^{k-1}\varphi(p) ）\
3.积性函数：若 p,q 互质，则有 \varphi(pq)=\varphi(p)\varphi(q) （证明参考 剩余系的复合）
筛法计算
若 i 是质数，则 \varphi(i)=i-1 。
若 i 是合数，则 i 在线性筛中被自己的 最小质因子 筛掉。
设 n 为 i 的最小质因子，i=nm 。
若 n\mid m ，则 m 包含 i 的所有质因子，nm\prod_{k=1}^s\dfrac{p_k-1}{p_k}=n\varphi(m)
若 n\nmid m ，则 n,m 互质，由性质 1,3，得 \varphi(i)=\varphi(n)\varphi(m)=(n-1)\varphi(m) 。
性质
::::info[证明]
则有
\mu(x)=\begin{cases}1&x=1\\0&\sum_{i=1}^s a_i\not=s\\(-1)^s&x\not=1,\sum_{i-1}^s a_i=s\end{cases}
其中 \sum_{i-1}^s a_i=s 的条件即 x 不含相同质因子。
筛法计算
若 i 是质数，则 \mu(i)=-1 。
若 i 是合数，则 i 在线性筛中被自己的 最小质因子 筛掉。
设 n 为 i 的最小质因子，i=nm 。
若 n\mid m ，则 i 有两个质因子 n ，\mu(i)=0
若 n\nmid m ，则 i 比 m 多一个质因子 n ，\mu(i)=-\mu(m)
两个性质
性质1
::::info[证明]
在 x=1 时，易证。
在 x\not= 1 时，根据唯一分解定理，有 x=\prod_{i=1}^s p_i^{a_i} ，由于在 x 有相同质因子时 \mu(x)=0 ，因此可以构造 x'=\prod_{i=1}^sp_i 使得 \sum_{d\mid x}\mu(d)=\sum_{d\mid x'}\mu(d) 。则：
不含质因子的 d （即 1 ）有 C_s^0 个，\mu(d) 为正；
含一个质因子的 d 有 C_s^1 个，\mu(d) 为负；
含两个质因子的 d 有 C_s^2 个，\mu(d) 为正；
\dots
于是 \sum_{d\mid x'}\mu(d)=\sum_{i=0}^s(-1)^s C_s^i ，由二项式定理，\sum_{i=0}^s(-1)^s C_s^i=(1-1)^s=0 。
::::
性质2
::::info[证明]
在 x=1 时，易证。
在 x\not= 1 时，同上文构造 x'=\prod_{i=1}^sp_i 使得 \sum_{d\mid x}\mu(d)\dfrac{x}{d}=\sum_{d\mid x'}\mu(d)\dfrac{x'}{d}=x'\sum_{d\mid x'}\dfrac{\mu(d)}{d} 。又有 x'\sum_{d\mid x'}\dfrac{\mu(d)}{d}=x(1-(\dfrac{1}{p_1}+\dfrac{1}{p_2}+\dots)+(\dfrac{1}{p_1p_2}+\dfrac{1}{p_2p_3}+\dots)-\dots) （这步即通过 \mu(d) 的定义判断 \dfrac{\mu(d)}{d} 的正负性），因式分解得 x(1-(\dfrac{1}{p_1}+\dfrac{1}{p_2}+\dots)+(\dfrac{1}{p_1p_2}+\dfrac{1}{p_2p_3}+\dots)-\dots)=x'\prod_{i=1}^s1-\dfrac{1}{p_i} ，即 \varphi(x) 。
::::
狄利克雷卷积
定义
对于两个 积性函数 f(x),g(x) ，有
(f\ast g)(x)=\sum_{d\mid x} f(d)g(\dfrac{x}{d})
常见积性函数
元函数 \varepsilon(x)=[x=1] ；
常数函数 1(x)=1 ；
恒等函数 id(x)=x 。
常见卷积关系
1.\sum_{d\mid x}\mu(d)=[x=1]\Leftrightarrow (\mu\ast 1)(x)=\varepsilon(x) \
2.\sum_{d\mid x}\varphi(d)=x\Leftrightarrow (\varphi\ast 1)(x)=id(x) \
3.\sum_{d\mid x}\mu(d)\dfrac{x}{d}=\varphi(x)\Leftrightarrow (\mu\ast id)(x)=\varphi(x) \
4.对于任意积性函数 f ，有 (f\ast \varepsilon)(x)=f(x) \
5.对于任意积性函数 f ，有 (f\ast 1)(x)\not=f(x)
证明考虑狄利克雷卷积即可，此处省略。
和式的变换
和式即类似 \sum_{k\in K} a_k 的形式的式子。
这里设 n<m 。
替换条件式
容易理解，若 $i,j$ 均整除 $d$，则 $d$ 至少包含 $i,j$ 的一个公因数，即 $\gcd(i,j)\mid d$。
### 替换指标变量
$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]=\sum_{id=1}^n\sum_{jd=1}^m [\gcd(id,jd)=d]$。
$\sum_{id=1}^n$ 和 $\sum_{jd=1}^m$ 都是在枚举 $d$ 的倍数，故当 $i,j$ 互质时，$\gcd(id,jd)=d$。
### 交换求和顺序
$\sum_{i=1}^n\sum_{j=1}^m F(i)G(j)=\sum_{j=1}^m\sum_{i=1}^n F(i)G(j)$。
易证。
### 分离变量
$\sum_{i=1}^n\sum_{j=1}^m F(i)G(j)=\sum_{j=1}^m F(i)\sum_{i=1}^n G(j)$。
证明考虑乘法交换律。
## 莫比乌斯反演
### 定义
对于两个 **积性函数** $f(x),g(x)$，有
$$f(x)=\sum_{d\mid x} g(d)\Leftrightarrow g(x)=\sum_{d\mid x}\mu(d)f(\dfrac{x}{d})$$
称 $f(x)$ 为 $g(x)$ 的莫比乌斯变换，$g(x)$ 为 $f(x)$ 的莫比乌斯逆变换。
### 证明
有 $f(x)=\sum_{d\mid x}g(x)1(\dfrac{x}{d})=(g\ast 1)(x),g(x)=\sum_{d\mid x}\mu(d)f(\dfrac{x}{d})=(\mu\ast f)(x)$（狄利克雷卷积）。
若左式成立，有 $f(x)=(g\ast 1)(x)$，则 $g(x)=(\mu\ast f)(x)=(\mu\ast g\ast 1)(x)=((\mu\ast 1)\ast g)(x)=(\varepsilon\ast g)(x)=g(x)$，即右式也成立；
若右式成立，有 $g(x)=(\mu\ast f)(x)$，则 $f(x)=(g\ast 1)(x)=(\mu\ast f\ast 1)(x)=((\mu\ast 1)\ast f)(x)=(\varepsilon\ast f)(x)=f(x)$，即左式也成立。
### 应用
e.g. [题目传送门](https://www.luogu.com.cn/problem/P1829)。
即给定 $n,m$，求 $\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i,j)\pmod{20101009}$。
::::info[解法]
开始推式子。
不妨钦定 $n<m$。
原式即 $\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\gcd(i,j)}$，将 $\gcd(i,j)$ 单独拎出来，得
$$\sum_{i=1}^n\sum_{j=1}^mij\sum_{d=1}^n\dfrac{[\gcd(i,j)=d]}{d}$$
交换求和顺序，则有 $\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^mij\dfrac{[\gcd(i,j)=d]}{d}$，替换指标变量，得
$$\sum_{d=1}^n\sum_{id=1}^n\sum_{jd=1}^mijd^2\dfrac{[\gcd(id,jd)=d]}{d}$$
$id$ 上限为 $n$，则 $i$ 上限为 $n/d$，$j$ 同理（之后统称为修改上限）得
$$\sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ijd[\gcd(i,j)=1]$$
将 $\gcd(i,j)$ 代入 $\sum_{k\mid x}\mu(x)=[x=1]$ 中，得
$$\sum_{k\mid \gcd(i,j)}\mu(\gcd(i,j))=[\gcd(i,j)=1]$$
代入上式，得
$$\sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ijd\sum_{k\mid \gcd(i,j)}\mu(k)$$
替换条件式，得
$$\sum_{d=1}^n\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}ijd\sum_{k=1}^{n/d}\mu(k)[k\mid i][k\mid j]$$
交换求和顺序并分离变量，得
$$\sum_{d=1}^nd\sum_{k=1}^{n/d}\mu(k)\sum_{i=1}^{n/d}i[k\mid i]\sum_{j=1}^{m/d}j[k\mid j]$$
替换指标变量，得
$$\sum_{d=1}^nd\sum_{k=1}^{n/d}\mu(k)\sum_{ik=1}^{n/d}ik\sum_{jk=1}^{m/d}jk$$
分离变量并修改上限，得
$$\sum_{d=1}^nd\sum_{k=1}^{n/d}\mu(k)k^2\sum_{i=1}^{n/dk}i\sum_{j=1}^{m/dk}j$$
$\mu(k)$ 显然可以通过预处理线性求出，所以只用先对 $d$ 整除分块，然后套一个对 $k$ 的整除分块即可。
::::
## 杜教筛
给定积性函数 $f(x)$，求 $s(n)=\sum_{i=1}^n f(i)$。
### 解法
构造积性函数 $g(x)$，使得 $(f\ast g)(x)$ 的前缀和容易计算。
根据递推式
$$g(1)s(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^n g(i)s(n/i)$$
递归计算 $s(n)$ 即可。
::::info[证明]
下面证明递推式 $g(1)s(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^n g(i)s(n/i)$ 成立。
现在有 $\sum_{i=1}^n(f\ast g)(i)$，狄利克雷卷积得
$$\sum_{i=1}^n\sum_{i\mid d}f(\dfrac{i}{d})g(d)$$
替换条件式得
$$\sum_{i=1}^n\sum_{d=1}^n[i\mid d]f(\dfrac{i}{d})g(d)$$
交换求和顺序得
$$\sum_{d=1}^n\sum_{i=1}^n[i\mid d]f(\dfrac{i}{d})g(d)$$
替换指标变量得
$$\sum_{d=1}^n\sum_{id=1}^n[id\mid d]f(\dfrac{id}{d})g(d)$$
即
$$\sum_{d=1}^n\sum_{id=1}^n f(i)g(d)$$
修改上限得
$$\sum_{d=1}^n\sum_{i=1}^{n/d} f(i)g(d)$$
分离变量得
$$\sum_{d=1}^n g(d)\sum_{i=1}^{n/d} f(i)$$
将 $s(n/d)=\sum_{i=1}^{n/d}f(i)$ 代入上式得
$$\sum_{d=1}^n g(d)s(n/d)$$
将 $i=1$ 时的项分离出来得
$$g(1)s(n)+\sum_{i=2}^n g(i)s(n/i)$$
即
$$g(1)s(n)=\sum_{i=1}^n(f\ast g)(i)-\sum_{i=2}^n g(i)s(n/i)$$
::::
#### 优化
1.使用线性筛预处理较小的 $s(n)$；\
2.记忆化防止重复计算；\
3.使用整除分块做 $s(n/i)$ 的递归。
### 应用
[很板的](https://www.luogu.com.cn/problem/P4213)。
有 $(\varphi\ast 1)(x)=id(x)$，注意这里 $1(x)$ 是常数函数。
则有 $s(n)=1(1)s(n)=\sum_{i=1}^nid(i)-\sum_{i=2}^n 1(i)s(n/i)=\sum_{i=1}^n i-\sum_{i=2}^n s(n/i)=\dfrac{(n+1)n}{2}-\sum_{i=2}^n s(n/i)$。
有 $(\mu\ast 1)(x)=\varepsilon(x)$。
则有 $s(n)=1(1)s(n)=\sum_{i=1}^n\varepsilon(i)-\sum_{i=2}^ns(n/i)=1-\sum_{i=2}^ns(n/i)$。
## 例题
### P11480
先考虑全部圣诞老人来到的情况，根据经典结论，编号为 $a^2$ 的灯会被关闭。
若仅改变编号为 $t$ 的灯的状态，那么需要改变的灯的编号为满足 $at\le n$ 且 $\mu(a)\not= 0$ 的 $at$。这样对于第 $it$ 盏灯，它就会被改变 $\sum_{d\mid i} [\mu(d)\not= 0]$ 次，由于有 $\sum_{d\mid i} \mu(d)=[i=1]$，所以除了 $t$ 之外，编号为 $it$ 的灯都会被改变偶数次。
那么仅改变编号为 $j^2(j\not= 1)$ 的灯，第 $i$ 盏灯就需要改变 $\sum_{j=2}^{\sqrt{j}}[j^2\mid i\land\mu(\dfrac{i}{j^2})\not= 0]$ 次，其中 $\land$ 表示两边的条件需要同时成立。可以发现 $j^2\mid i\land\mu(\dfrac{i}{j^2})\not= 0$ 即要求 $j^2$ 是 $i$ 的因数且 $\dfrac{i}{j^2}$ 没有其它因子是完全平方数，也就是确定了唯一的 $j$。
于是只有在 $i$ 对应的 $j=1$ 时，$\sum_{j=2}^{\sqrt{j}}[j^2\mid i\land\mu(\dfrac{i}{j^2})\not= 0]$ 的值才为 $0$。因此来到的圣诞老人 $i$ 没有相同质因子，即 $\mu(i)=0$，总数为 $\sum_{i=1}^n \mu^2(i)=\sum_{i=1}^{\sqrt{n}}\mu(i)\left\lfloor\dfrac{n}{i^2}\right\rfloor$。
杜教筛求解即可。
### P10186
引理 1：
在 $n^2$ 点阵中，若直线第一个穿过 $(x,y)$ ，则直线会穿过 $n/\max(x,y)$ 个点。
引理 2：
若直线穿过的第一个点为 $(x,y)$，则 $\gcd(x,y)=1$。
这两个引理比较简单，读者自证不难。
因此对角线一边的答案（另一边是镜像的）就是 $\sum_{i=1}^n \sum_{j=1}^{i-1} (n/\max(i,j))^2[\gcd(i,j)=1]$，由于 $j$ 的上限是 $i-1$，故 $\max(i,j)=i$。
然后用和式的变换可以化出 $\sum_{i=1}^n (n/i)^2\sum_{j=1}^{i-1} [\gcd(i,j)=1]$ 观察到后面的 $\sum_{j=1}^{i-1} [\gcd(i,j)=1]$ 其实就是 $\varphi(i)$，因此原式就是 $\sum_{i=1}^n \varphi(i) (n/i)^2$。
对角线上有 $n$ 个点，贡献就是 $n^2$。
于是答案就是 $n^2+2\sum_{i=1}^n \varphi(i) (n/i)^2$。$n/i$ 可以整除分块，$\varphi(i)$ 前缀和可以用杜教筛。
### 一些练习题
[P1891](https://www.luogu.com.cn/problem/P1891)、[P3601](https://www.luogu.com.cn/problem/P3601)、[P3768](https://www.luogu.com.cn/problem/P3768)、[P10584](https://www.luogu.com.cn/problem/P10584)