Dirichlet 卷积
定义
$$ (f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d}) $$
性质
$$ (f*g)*h=f*(g*h)\\ f*(g+h)=f*g+f*h\\ f*g=g*f\\ f*\epsilon=\epsilon*f=f\\ $$
若 $f,g$ 为积性函数，则 $f*g$ 为积性函数
常见的 Dirichlet 卷积
$$ d=1*1\\ \sigma=\mathrm{id}*1\\ \mathrm{id}=\varphi*1\\ \epsilon=\mu*1 $$
即
$$ d(n) = \sum_{d|n}1\\ \sigma(n) = \sum_{d|n}d\\ \sum_{d|n}\varphi(d)=n\\ \sum_{d|n}\mu(d)=[n=1] $$
$\epsilon=\mu*1$ 的证明：
$n=1$ 显然。假设 $n>1$ 有 $k\ge 1$ 个不同质因子。只考虑 $\mu(d)\ne 0$ 的 $d$。则:
$$ \sum_{d|n}\mu(d)=\sum_{i=0}^k(-1)^iC_{i}^{k} $$
由二项式定理得上式为 $1$.
莫比乌斯反演
若数论函数 $f,g$ 对所有 $n\ge 1$ 满足：
$$g(n)=\sum_{d|n}f(d)$$
则对于所有 $n\ge 1$ 满足：
$$f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})$$
一个技巧
给定 $g(1)\sim g(n)$，求 $f(1)\sim f(n)$.
for (int i = 1; i <= n; i ++ )
for (int j = i + i; j <= n; j += i)
a[j] -= a[i];
用上述方法，不用线性筛也可以求出 $\varphi,\mu$.
例题
例题 $1$
已知 $f(1)\sim f(n)$.
定义：
$$ f_k(n)=\sum_{d_1d_2\cdots d_k=n}f(d_1)f(d_2)\cdots f(d_k) $$
求 $f_k(1)\sim f_k(n)$.
$n,k\le 10^5$.
解
注意到 $f_2$ 即为 Dirichlet 卷积，即 $f_2=f*f$.
由此想到 $f_k=f*f*f*\cdots*f$. 故直接快速幂即可。
例题 $2$
定义
$$ S(n)=\left\{d|\gcd(d,\frac{n}{d})=1 \right\}\\ f(n)=\sum_{d\in S(n)} d^2 $$
求
$f(10^7!)\bmod (10^9+9)$
解
注意到 $(a,b)=1$ 的充要条件是 $a,b$ 没有共同的质因数。
我们把 $n,d$ 分解出来：
$$ n=\prod_{i=1}^mp_i^{c_i} d=\prod_{i=1}^mp_i^{c_i} $$
则 $e_i=0/c_i$，即要么不选要么全选。写的严谨一点就是说：
考虑 $n$ 中的质因子 $p^k$，则容易看出 $[p\nmid d]$ 和 $[p^k|d]$ 其中之一成立。
而
$$ f(n)=\prod_{i=1}^m\left(1+(p_i^{c_i})^2\right) $$
类比 $\sigma_2(n)$ 可以看出 $f$ 是积性函数。显然，$f(p^k)=p^{2k}+1$.
于是将 $(10^7)!$ 分解质因数即可。因为是提交答案题，所以时间复杂度可以接受。
分解阶乘的具体方法可参考 这一题。
例题 $3$
给定正整数 $n$，求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。
$1\le n\le 10^7$。
解
简单题。
$$ \mathrm{res}=\sum_{p\in \mathrm{prime}}\sum_{1\le i\le n}\sum_{j\le i\le n}[\gcd(i,j)=p] $$
用经典 trick 把式子变形：
$$ \begin{aligned} \mathrm{res}&=\sum_{p\in \mathrm{prime}}\sum_{1\le i\le \frac{n}{p}}\sum_{1\le j\le \frac{n}{p}}\\ &=\sum_{p\in \mathrm{prime}} \left(\left(\sum_{1\le i\le \frac{n}{p}} 2\times \varphi(i)\right)-1\right) \end{aligned} $$
直接线性筛求 $\varphi$ 的前缀和即可。
例题 $4$
设
$$ f(n)=\left(\sum_{i=1}^n\varphi(n^i)\right)\bmod (n+1)\\ g(n)=\sum_{i=1}^nf(i) $$
求 $g(5\times 10^8)$.
解
考虑
$$\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$$
所以
$$\varphi(n^k)=n^k\prod_{p|n}\left(1-\frac{1}{p}\right)=n^{k-1}\varphi(n)$$
又 $n\equiv-1(\mathrm{mod}~(n+1))$，因此
$$ \varphi(n^k)\equiv(-1)^{k-1}\varphi(n) (\mathrm{mod}~(n+1)) f(n)=\varphi(n)\sum_{i=1}^n(-1)^{i-1} $$
当 $n$ 是奇数，$f(n)=\varphi(n)$；否则 $f(n)=0$。线性筛求解即可。
例题 $5$
对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $a \le x \le b$，$c \le y \le d$，且 $\gcd(x,y) = k$，$\gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。
$1 \le n,k \le 5 \times 10^4$，$1 \le a \le b \le 5 \times 10^4$，$1 \le c \le d \le 5 \times 10^4$。
解
注意到我们可以用差分把问题转换为：
对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $1 \le x \le n$，$1 \le y \le m$，且 $\gcd(x,y) = k$。
根据前面提到的 trick，可以把答案转换为
$$ T(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\epsilon(\gcd(i,j)) $$
根据 $\epsilon=1*u$，容易得到答案为
$$ \sum_{d}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor $$
数论分块优化即可。
如果还没看懂可以看看 这个.
例题 $6$
给定 $n,m,k$，计算
$$\sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k$$
对 $10^9 + 7$ 取模的结果。
$T$ 是数据组数。$1 \leq T \leq 2 \times 10^3$，$1 \leq n, m, k \leq 5 \times 10^6$。
解
$$ \begin{aligned} \mathrm{res}&=\sum_d d^k\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\\ &= \sum_{d_1}d_1^k\sum_{i=1}^{\frac{n}{d_1}}\sum_{j=1}^{\frac{n}{d_1}}\sum_{d_2|\gcd(i,j)}\mu(d2)\\ &= \sum_{d_1}d_1^k\sum_{d_2}\mu(d_2)\sum_{i=1}^{\left\lfloor\frac{\left\lfloor \frac{n}{d1} \right\rfloor}{d2}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{\left\lfloor \frac{m}{d1} \right\rfloor}{d2}\right\rfloor}1\\ &= \sum_{d_1}d_1^k\sum_{d_2}\mu(d_2)\left\lfloor\frac{n}{d_1 d_2}\right\rfloor\left\lfloor\frac{m}{d_1d_2}\right\rfloor \end{aligned} $$
令 $f(n)=\sum_{d|n}d^k\mu(\frac{n}{d})$. 注意到 $f=\mathrm{id}_k*\mu$，所以 $f$ 是积性函数。
$$ f(p^a)=\mu(1)\mathrm{id}_k(p^a)+\mu(p)\mathrm{id}_k(p^{a-1})=p^{ak}-p^{(a-1)k}. $$
线性筛出 $f$ 即可。
