《算法竞赛中的初等数论》（三）正文 0x30 积性函数（ACM / OI / MO）（十五万字符数论书）

整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

写在最前面：本文部分内容来自网上各大博客或是各类图书，由我个人整理，增加些许见解，仅做学习交流使用，无任何商业用途。因个人实力时间等原因，本文并非完全原创，请大家见谅。

《算法竞赛中的初等数论》正文 0x00整除、0x10 整除相关（ACM / OI / MO）（十五万字符数论书）

《算法竞赛中的初等数论》（信奥 / 数竞 / ACM）前言、后记、目录索引（十五万字符的数论书）

全文目录索引链接： https://fanfansann.blog.csdn.net/article/details/113765056

---

本章内容不多，比较简单，非常基础，建议完全掌握，包括所有的概念和证明。

0x30 积性函数

一些定义

• 数论函数
  定义域为正整数的函数称为数论函数。

• 积性函数
  对于数论函数 $f$，若任意互质的 $p,q$ 都有 $f(pq)=f(p)f(q)$，则称 $f$ 是积性函数。

• 完全积性函数
  对于数论函数 $f$，若任意 $p,q$ 都有 $f(pq)=f(p)f(q)$，则称 $f$ 是完全积性函数

• 定义逐点加法
  $(f+g)(x)=f(x)+g(x)$，$(f\cdot g)(x)=f(x)g(x)$

定理30.1： 积性函数一定满足 $f(1)=1$。

---

考虑证明：

显然 $1$ 与任何数都互质，满足积性函数的定义，那么我们假设存在一个正整数 $a$ 满足 $f(a)!=0$，显然有：$f(a)=f(1\ast a)=f(1)$，两端同除 $f(a)$ ，得：$f(1)=1$，性质得证 □

---

定理30.2： 对于一个大于 $1$的正整数 $N$ ，根据唯一分解定理有 $N=\prod p_i^{a_i}$ ，则对于任意积性函数 $f$ ，有： $f(N)=f(\prod p_i^{a_i})=\prod f(p_i^{a_i})$若 $f$完全积性，则 $f(N)=\prod f(p_i{)}^{a_i}$。

由此可得推论：凡是积性函数均可用线性筛法求解

性质30.3： 对于一个大于 $1$ 的整数由唯一分解定理有： $n=\prod p_i^{a_i}$，其中 $p_i$ 为互不相同的素数。

• 那么对于一个积性函数 $f$，$f(n)=f(\prod p_i^{a_i})=\prod f(p_i^{a_i})$

• 对于一个完全积性函数 $f$，$f(n)=\prod f(p_i{)}^{a_i}$

性质30.4： 若 $f$，$g$ 为积性函数，则 $f\ast g$ 也为积性函数。

0x31 常见积性函数

• $\phi (n)$ －欧拉函数 $\phi (n)=\sum _{i=1}^n[i\perp n]$

• $\mu (n)$ －莫比乌斯函数，关于非平方数的质因子数目

• $gcd(n,k)$ －最大公因数，当 $k$ 固定的情况

• $d(n)$ －$n$ 的正因子数目 $d(n)=\sum _{i|n}1$

• $\sigma (n)$ －$n$ 的所有正因子之和 $\sigma (n)=\sum _{d|n}d$

• $\sigma k(n)$ － 因子函数，$n$ 的所有正因子的 $k$ 次幂之和，当中 $k$ 可为任何复数。

• $1(n)$ －不变的函数，定义为 $1(n)=1$ （完全积性）

• $id(n)$ －单位函数（恒等函数），定义为 $id(n)=n$（完全积性）

• $idk(n)$ －幂函数，对于任何复数、实数 $k$，定义为 $idk(n)=n^k$ （完全积性）

• $\epsilon (n)$ －定义为：$\epsilon (n)=[n=1]$，若$n=1$，$\epsilon (n)=1$；若 $n>1$，$\epsilon (n)=0$ 。即： 对于狄利克雷卷积的乘法单位 / 狄利克雷特卷积的单位元，（完全积性）

• $\lambda (n)$ －刘维尔函数，关于能整除 $n$ 的质因子的数目

• $\gamma (n)$，定义为 $\gamma (n)=(-1{)}^{\omega }(n)$，在此加性函数 $\omega (n)$ 是不同能整除 $n$ 的质数的数目

• 另外，所有狄利克雷特征均是完全积性的。

积性函数的逆元： 对每个 $f(1)\ne 0$ 的积性函数 $f$ ，都存在一个函数 $g$ 使得 $f\ast g=ϵ$，则称函数 $g$ 为 函数 $f$ 的逆元。

---

根据定义显然有

ϵ = g ∗ f [ n = 1 ] = ∑ i ∣ n f ( i )   g ( n i ) [ n = 1 ] = f ( 1 )   g ( n ) + ∑ i ∣ n , i ≠ 1   f ( i )   g ( n i )

$$\begin{aligned}\epsilon&=g*f\\ [n=1]& =\quad\sum_{i\mid n} f(i) \ g\left(\frac{n}{i}\right)\\ [n=1]&= f(1) \ g(n)+\sum_{i\mid n,i\neq1}\ f(i)\ g\left(\frac {n}{i}\right)\\& \end{aligned}$$ ϵ[n=1][n=1]​=g∗f=i∣n∑​f(i) g(in​)=f(1) g(n)+i∣n,i​=1∑​ f(i) g(in​)​

化简即可得到：

$$g(n)=\frac{[n=1]-\sum _{i\mid n,i\ne 1}f(i)g(\frac{n}{i})}{f(1)}$$
​

积性函数 欧拉函数 已在 0x14.1 欧拉函数 中讲解过，这里不再赘述。

​

0x32 莫比乌斯函数

定义

μ ( n ) = { 0 ∃ i ∈ [ 1 , m ] , C i > 1 ( − 1 ) m ∀ i ∈ [ 1 , m ] , C i = 1 \mu(n) = \left\{

$$\begin{matrix} 0 & \exists i \in [1,m],C_i>1 \\ (-1)^m & \forall i \in [1,m],C_i=1 \end{matrix}$$ \right. μ(n)={ 0(−1)m​∃i∈[1,m],Ci​>1∀i∈[1,m],Ci​=1​

构造莫比乌斯函数

莫比乌斯函数可以理解为一个容斥原理的映射

• 性质：
  $$\sum _{d|n}\mu (d)=[n=1]$$
  也可以表示为：$\epsilon =\mu \ast I$，其中 $\ast$ 是指 $Dirichlet$ 卷积。

（证明：使用唯一分解定理 + 二项式定理即可证明，这里不再展开）

• 补充结论：
  $$[gcd(i,j)=1]=\epsilon [gcd(i,j)]=\mu \ast I=\sum _{d|gcd(i,j)}\mu (d)$$
• 证明 $\mu (x)$ 是积性函数

$a=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_n^{{\alpha }_k}$

$b=p_1^{{\beta }_1}\times p_2^{{\beta }_2}\times \cdots \times p_n^{{\beta }_t}$

$a\times b=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_n^{{\alpha }_k}\times p_1^{{\beta }_1}\times p_2^{{\beta }_2}\times \cdots \times p_n^{{\beta }_t}$

若 $\mu (a)=0$或 $\mu (b)=0$，则 $\mu (a\times b)=0$（因为均含$\alpha \text{or}\beta >1$）

即 $\mu (a\times b)=\mu (a)\times \mu (b)$

若 $\mu (a)\ne 0$或$\mu (b)\ne 0$，则$\mu (a\times b)=(-1{)}^{k+t}=(-1{)}^k\times (-1{)}^t=\mu (a)\times \mu (b)$

0x33 狄利克雷卷积

• 定义： 若函数$f,g$为积性函数，则定义 $f,g$ 的狄利克雷卷积为：

$$f\ast g(n)=\sum _{d|n}f(d)g(\frac{n}{d})$$

计算的时候可以把枚举约数转换成枚举倍数，以调和级数 $O(nlogn)$ 的复杂度求出 $f\ast g$ 的前 $n$ 项。详见本文 0x33.2 $O(nlogn)$ 的卷积预处理

• 满足性质：

交换律：
$$f\ast g(n)=\sum _{d|n}f(d)g(\frac{n}{d})=\sum _{d|n}g(d)f(\frac{n}{d})=g\ast f(n)$$

结合律：

$$f\ast g\ast h(n)=\sum _{d|n}f(d)\sum _{t|\frac{n}{d}}g(t)h(\frac{n}{dt})=\sum _{d_1{d}_2{d}_3=n}f(d_1)g(d_2)h(d_3)=f\ast (g\ast h)(n)$$

分配律： $f\ast (g+h)=f\ast g+f\ast h$

单位元：$f\ast \epsilon =f$

重要性质： 若函数$f,g$为积性函数，则$f\ast g$也为积性函数（ * 为狄利克雷特卷积）

---

0x33.1 常见积性函数的卷积

性质0x33.1：$\forall f(n),e\ast f(n)=f(n)$

性质0x33.2：$1\ast 1(n)={\sum }_{d|n}1=d(n)$

性质0x33.3：$id\ast 1(n)={\sum }_{d|n}d=\sigma (n)$

性质0x33.4：$\mu \ast 1(n)={\sum }_{d|n}\mu (d)\times 1(\frac{n}{d})=[n=1]=\epsilon (n)$

性质0x33.4证明：

由唯一分解定理： $n=p_1^{k_1}{p}_2^{k_2}\dots p_m^{k_m}$

代入上式得：
μ ∗ 1 ( n ) = ∑ d ∣ n μ ( d ) × 1 ( n d ) = ∑ C 1 = 0 k 1 ∑ C 2 = 0 k 2 ⋯ ∑ C m = 0 k m μ ( p 1 C 1 p 2 C 2 … p m C m )

$$\begin{aligned}\mu*1(n)&=\sum_{d|n}\mu(d)\times 1(\cfrac{n}{d})\\&=\sum_{C_1=0}^{k_1}\sum_{C_2=0}^{k_2}\dots\sum_{C_m=0}^{k_m}\mu(p_1^{C_1}p_2^{C_2}\dots p_m^{C_m})\end{aligned}$$ μ∗1(n)​=d∣n∑​μ(d)×1(dn​)=C1​=0∑k1​​C2​=0∑k2​​⋯Cm​=0∑km​​μ(p1C1​​p2C2​​…pmCm​​)​

我们分析该和式的实际意义，显然当某个质因子数量 $c_i>1$，则 $\mu$ 的值为 $0$。
这样的话，我们就可以去掉无用的枚举（$\mu =0$），利用二项式定理证明：

μ ∗ 1 ( n ) = ∑ C 1 = 0 1 ∑ C 2 = 0 1 ⋯ ∑ C m = 0 1 μ ( p 1 C 1 p 2 C 2 … p m c m ) = ∑ C 1 = 0 1 ∑ C 2 = 0 1 ⋯ ∑ C m = 0 1 ( − 1 ) ∑ i = 1 m C i = ∑ i = 0 m ( − 1 ) i ( m i ) = [ m = 0 ] = [ n = 1 ] = ε ( n )

$$\begin{aligned}\mu*1(n)&=\sum_{C_1=0}^1\sum_{C_2=0}^1\dots\sum_{C_m=0}^1\mu(p_1^{C_1}p_2^{C_2}\dots p_m^{c_m}) \\&=\sum_{C_1=0}^1\sum_{C_2=0}^1\dots\sum_{C_m=0}^1(-1)^{\sum_{i=1}^m C_i}\\&=\sum_{i=0}^m(-1)^i\dbinom mi\\&=[m=0]=[n=1]=\varepsilon(n)\end{aligned}$$ μ∗1(n)​=C1​=0∑1​C2​=0∑1​⋯Cm​=0∑1​μ(p1C1​​p2C2​​…pmcm​​)=C1​=0∑1​C2​=0∑1​⋯Cm​=0∑1​(−1)∑i=1m​Ci​=i=0∑m​(−1)i(im​)=[m=0]=[n=1]=ε(n)​

性质0x33.5：$\phi \ast 1(n)={\sum }_{d|n}\phi (d)=n=id(n)$

性质0x33.5证明：
∵ φ = μ ∗ i d , ϵ = μ ∗ 1 ∴ 1 ∗ φ = 1 ∗ μ ∗ i d ∴ 1 ∗ φ = ϵ ∗ i d = i d ( n ) ∴ ∑ d ∣ n φ ( d ) = n

$$\begin{aligned}&∵\varphi = \mu * id,\epsilon = \mu * 1\\&∴1 * \varphi = 1 * \mu * id\\&∴1 * \varphi = \epsilon * id = id(n)\\&∴\sum_{d | n} \varphi (d) = n\end{aligned}$$ ​∵φ=μ∗id,ϵ=μ∗1∴1∗φ=1∗μ∗id∴1∗φ=ϵ∗id=id(n)∴d∣n∑​φ(d)=n​

积性函数的转换关系：

$$\mu {\Rightarrow }^{\ast 1}\Rightarrow \epsilon {\Rightarrow }^{\ast 1}\Rightarrow 1{\Rightarrow }^{\ast 1}\Rightarrow d$$

$$\phi {\Rightarrow }^{\ast 1}\Rightarrow id{\Rightarrow }^{\ast 1}\Rightarrow \sigma$$

反方向的转换关系：

$$\mu {\Leftarrow }^{\ast \mu }\Leftarrow \epsilon {\Leftarrow }^{\ast \mu }\Leftarrow 1{\Leftarrow }^{\ast \mu }\Leftarrow d$$

$$\phi {\Leftarrow }^{\ast \mu }\Leftarrow id{\Leftarrow }^{\ast \mu }\Leftarrow \sigma$$

0x33.2 $O(nlogn)$ 的卷积预处理

若已知数论函数 $f,g$ ，我么可以将枚举约数转换成枚举倍数，以调和级数 $O(nlogn)$ 的复杂度求出 $f\ast g$ 的前 $n$ 项 ：

$$h(n)=f\ast g(n)=\sum _{d|n}f(d)g(\frac{n}{d})$$

int f[N], g[N], h[N];
inline void init(int n) {
   
    for (int i = 1; i * i <= n; i++) {
   
        for (int j = i; i * j <= n; j++) {
   
            if (j == i) h[i * j] += f[i] * g[i];
            else h[i * j] += f[i] * g[j] + f[j] * g[i];
        }
    }
}

• 竞赛例题选讲

Problem A. Longge的问题 （BZOJ 2705[SDOI2012]）

Problem

Solution

Code

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 50007;

int n, m, t;
int ans;

int get_phi(int n)
{
   
    int ans = n;
    for(int i = 2; i * i <= n; ++ i) {
   
        if(n % i == 0) {
   
            ans = ans / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}

signed main()
{
   
    scanf("%lld", &n);
    int ans = 0;
    for(int i = 1; i * i <= n; ++ i) {
   
        if(n % i == 0) {
   
            ans += n / i * get_phi(i);
            if(i * i != n) {
   
                ans += i * get_phi(n / i);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Problem B. Clarke and math（HDU 5628 ）

给定 $f(i)$，$(i=1,2,\dots ,n)$

求：

$$g(i)=\sum _{i_1\mid i}\sum _{i_2\mid i_1}\sum _{i_3\mid i_2}\cdots \sum _{i_k\mid i_{k-1}}f(i_k)\mathrm{m}\mathrm{o}\mathrm{d}1000000007(1\le i\le n)$$

Solution

显然题目中要求的式子就是 $f\ast 1^k$，使用快速幂加速即可。

Code

待更…

Problem C.

---

建议阅读的拓展内容：浅谈一类积性函数的前缀和

%https://blog.csdn.net/qq_37451344/article/details/81843722?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-13.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-13.control

%https://www.cnblogs.com/Milkor/p/4474835.html

转载：https://blog.csdn.net/weixin_45697774/article/details/114975467