数论进阶

数论的一些反演

1.狄利克雷卷积

1.1积性函数

对于数论函数\(f\)，对任意互质的正整数\(p,q\)，满足\(f(pq)=f(p)f(q)\)，则称\(f\)为积性函数
对于数论函数\(f\)，对任意的正整数\(p,q\)，满足\(f(pq)=f(p)f(q)\)，则称\(f\)为完全积性函数
积性函数一定满足\(f(1)=1\)
对于任意大于\(1\)的正整数\(N\)和一个积性函数\(f\)，假设\(N=p_1^{a_1}p_2^{a_2}...p_n^{a_n}\)，那么\(f(N)=\prod_{i=1}^nf(p_i^{a_i})\)，如果\(f\)为完全积性函数，则有\(f(N)=\prod_{i=1}^nf(p_i)^{a_i}\)，由此可得凡是积性函数都可以用线性筛法求的
若\(f(x)\)和\(g(x)\)均为积性函数，则以下函数都是积性函数

\[h(x)=f(x^p)\\ h(x)=f^p(x)\\ h(x)=f(x)g(x)\\ h(x)=\sum_{d|x}f(d)g(\frac{x}{d}) \]

1.2常见积性函数

\(\varphi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})\) 欧拉函数：\(1\)到\(n\)中与\(n\)互质的数的个数
\(I(n)=1\) 不变函数
\(id(n)=n\) 恒等函数
\(\varepsilon(n)=[n==1]\)
\(\sigma(n)=\sum_{d|n}d\) \(n\)的所有正因子之和
\(d(n)=\sum_{d|n}1\) \(n\)的所有正因子的个数

1.3狄利克雷卷积

定义：若\(f,g\)均为积性函数，那么\(f,g\)的狄利克雷卷积为\(f*g(n)=\sum_{d|n}f(d)g(\frac{n}{d})\)

性质

交换律：\(f*g(n)=g*f(n)\)
结合律：\(f*g*h(n)=f*(g*h)(n)\)
分配律：\(f*(g+h)(n)=f*g+f*h\)
单位元：\(f*\varepsilon=f\)
\(f*g\)也为积性函数

1.4常见积性函数的卷积

\(I*I(n)=\sum_{d|n}1=d(n)\)
\(id*I(n)=\sum_{d|n}d=\sigma(n)\)
\(\mu*I(n)=\sum_{d|n}\mu(d)\times1=[n==1]=\varepsilon(n)\)

2.莫比乌斯反演

2.1莫比乌斯函数

\[n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}\\ \mu(n)= \begin{cases} (-1)^k\quad a_1=a_2=...=a_n=1 \\[2ex] 1 \ \ \ \ \ \ \ \ \ \quad n=1\\[2ex] 0 \ \ \ \ \ \ \ \ \ \quad otherwise \end{cases} \]

2.2莫比乌斯反演

设有两个数论函数\(F(n),f(n)\)，如果有\(F(n)=\sum_{d|n}f(d)\)

那么有

\(f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\)，
\(f(n)=\sum_{n|d}\mu(\frac{d}n)F(d)\)

证明：已知\(F=f*I\)，证明\(f=F*\mu\)

\[F*\mu=f*I*\mu=f*(I*\mu)=f*\varepsilon=f \]

2.3对莫比乌斯函数的一些理解

将一个数看做一个集合，它的每一个质因数为集合中的元素，莫比乌斯反演就是这样约数与倍数的加减容斥。

2.4常见反演技巧和公式

整除分块：对于任意一个\(i\)，找到最大的\(j\)，满足\(\lfloor \frac{i}{n}\rfloor=\lfloor \frac{j}{n}\rfloor\)，则\(j=\lfloor \frac{n}{\lfloor \frac{i}{n}\rfloor}\rfloor\)

枚举因子、倍数等。

\([gcd(i,j)==1]=\sum_{d|gcd(i,j)}\mu(d)\)
\(\sum_{i=1}^N\sum_{j=1}^M[gcd(i,j==k)]=\sum_{i=1}^{\lfloor \frac{N}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{M}{k} \rfloor}[gcd(i,j)==1]=\sum_{i=1}^{\lfloor \frac{N}{k} \rfloor}\sum_{j=1}^{\lfloor \frac{M}{k} \rfloor} \sum_{d|gcd(i,j)}\mu(d)=\sum_{d=1}^{min(\lfloor \frac{N}{k} \rfloor,\lfloor \frac{M}{k} \rfloor)}\mu(d)\lfloor \frac{N}{dk} \rfloor \lfloor \frac{M}{dk} \rfloor\)

参考链接
算法竞赛中的初等数论

算法复习