前置知识

　　积性函数

　　　　积性函数指对于所有互质的整数$a$和$b$有性质$f(ab)=f(a)f(b)$的数论函数。若对于所有整数$a$和$b$都有性质$f(ab)=f(a)f(b)$成立，则称$f(n)$是完全积性的。例如$\phi (n)$为积性函数。

　　数论函数

　　　　定义

　　　　数论函数（或称算术函数）指定义域为正整数的函数。

　　　　例子

　　　　1）单位函数$\epsilon(n)=[n=1]$

　　　　　　$[A]$表示$A$为真时为1，否则为0

　　　　2）常值函数$1(n)=1$

　　　　3）恒值函数$id(n)=n$

　　　　4）欧拉函数$\phi (n)=\sum^n_{i=1}[gcd(i,n)=1]$

　　　　若将$n$质因数分解有$\displaystyle n=\prod_{i=1}^{k}p_i^{c_i}$，则$\displaystyle\phi (n)=n\prod_{i=1}^{k}(1-\frac{1}{p_i})$（定义）

　　狄利克雷卷积

　　　　定义

　　　　对于任意两个数论函数$f,g$，它们的狄利克雷卷积为$h=f*g$

　　　　表示为：

$$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$$

　　　　或

$$(f*g)(n)=\sum_{i\times j=n}f(i)g(j)$$

　　　　性质

　　　　1）结合律$(f*g)*h=f*(g*h)$

　　　　2）分配律$f*(g+h)=f*g+f*h$

　　　　3）$(\alpha f)*g=\alpha (f*g)$

　　　　4）$\epsilon *f=f$

　　　　5）两个积性函数的卷积也为积性函数

　　　　性质的证明

　　　　1）结合律

　　　　　　$\displaystyle \begin{split} LHS &= [(f*g)*h](n)\\ &=\sum_{d\times k=n}(f*g)(d)h(k)\\ &=\sum_{d\times k=n}h(k)\sum_{i\times j=d}f(i)g(j)\\ &=\sum_{i\times j\times k=n}f(i)g(j)h(k)\end{split}$

　　　　　　同理$\displaystyle RHS=\sum_{i\times j\times k=n}f(i)g(j)h(k)$，故结论得证

　　　　2）分配律

　　　　　　$\displaystyle\begin{split}[f*(g+h)](n) &= \sum_{i \times j=n}f(i)(g+h)(j)\\ &= \sum_{i \times j=n}f(i) \cdot [g(j)+h(j)]\\ &= \sum_{i \times j=n}f(i)g(j)+ \sum_{i \times j=n}f(i)h(j)\\ &=(f*g + f*h)(n)\end{split}$

　　　　3）$\displaystyle LHS=\sum_{i \times j=n}(\alpha f(i))g(j)=\alpha\sum_{i \times j=n}f(i)g(j)=RHS$

　　　　4）$\displaystyle LHS=\sum_{i \times j=n}\epsilon (i)f(j)=\epsilon (1)f(n) + 0\cdot \sum_{d|n,d \neq n}f(d)=f(n)=RHS$

　　　　　　所以$\epsilon(n)$是狄利克雷卷积中的单位元

　　　　5）略

　　　　逆元

　　　　$f$的逆元记作$f^{-1}$其满足：$f*f^{-1}=\epsilon$

　　　　可以表达为：

$$\displaystyle{f^{-1}(n)=}\begin{cases} \displaystyle{\frac{1}{f(1)},} & \text{if }n=1\\ \displaystyle{-\frac{1}{f(1)} \sum_{d|n,d \neq 1}f^{-1}(\frac{n}{d})f(d)}, & \text{if }n \neq 1 \end{cases}$$

正文

　　莫比乌斯函数

　　　　定义

$$\mu (n)=\begin{cases} 1, & \text{n=1}\\ (-1)^{k}, & \text{n无大于1的平方数因数，且质因数分解n有}n=p_1p_2\cdots p_k\\ 0, & \text{n有大于1的平方因数}\end{cases}$$

　　　　性质

　　　　1）$\mu (n)$是积性函数。

　　　　2）$1*\mu=\epsilon$，即$\mu (n)$是常值函数$1(n)$的逆元

　　　　3）$\displaystyle\sum_{d|n}\frac{\mu (d)}{d}=\frac{\phi (n)}{n}$，即$id * \mu = \phi$

　　　　证明

　　　　性质一略。

　　　　对于性质二，若$n=1$，结论显然，若$n \neq 1$，设$n=\prod_{i=1}^{\alpha}p_i^{k_i}$

　　　　则$\displaystyle (\mu * 1)(n)=\sum_{d|n}\mu (d) = \binom{\alpha}{0} + \binom{\alpha}{1} \cdot (-1) + \binom{\alpha}{2} \cdot (-1)^{2} + \cdots + \binom{\alpha}{\alpha} \cdot (-1)^{\alpha}=[(-1) + 1]^{\alpha}=0$

　　　　对于性质三，当$n=p^{k}$,$p$为质数时，$\displaystyle\sum_{d|n}\frac{\mu (d)}{d} = \mu (1) + \frac{\mu (p)}{p} +\frac{\mu (p^2)}{p^2} + \cdots + \frac{\mu (p^k)}{p^k} = 1-\frac{1}{p} = \frac{\phi (n)}{n}$

当$n = \prod_{i=1}^{\alpha}p_{i}^{k_i}$,$p_i$为质数时，由积性函数性质，$\displaystyle\frac{\phi(n)}{n} = \prod_{i=1}^{\alpha}\phi (p_{i}^{k_i})=\prod_{i=1}^{\alpha} \sum_{d|p_{i}^{k_i}} \frac{\mu (d)}{d}=\sum_{d|n}\frac{\mu (d)}{d}$

　　　　线性筛求莫比乌斯函数值

　　　　略

　　莫比乌斯反演

　　　　若$f(n)=\sum_{d|n}g(d)$，则$g(n)=\sum_{d|n}\mu (d)f(\frac{n}{d})$，其中数论函数$f(n)$称为数论函数$g(n)$的莫比乌斯变换，数论函数$g(n)$称为数论函数$f(n)$的莫比乌斯逆变换（反演）

　　　　证明只需对$f$卷$\mu$即可

　　　　应用

　　　　求$\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)$

　　　　利用莫比乌斯函数的第二个性质，$[gcd(i,j)=1]=\epsilon (gcd(i,j))=\sum_{d|gcd(i,j)}\mu (d)$,所以

　　　　$\begin{split}\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j) &=\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{k=1}^{n} k \cdot [gcd(\lfloor\frac{i}{k}\rfloor, \lfloor\frac{j}{k}\rfloor)=1]\\ &= \sum_{k=1}^{n} \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} k[gcd(i,j)=1]\\ &= \sum_{k=1}^{n} k \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} \sum_{d|gcd(i,j)} \mu (d)\\ &= \sum_{k=1}^{n} k \sum_{d=1}^{n} \mu (d) \sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} [d|i] \sum_{j=1}^{\lfloor\frac{n}{k}\rfloor} [d|j] \\ &= \sum_{k=1}^{n} \sum_{d=1}^{n} k \mu (d) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{n}{kd}\rfloor \end{split}$

　　　　接下来对$k$进行数论分块即可，时间复杂度为$O(n^{\frac{3}{2}})$，对应的朴素算法时间复杂度$O(n^2logn)$（枚举$O(n^2)$$\times$辗转相除法$O(logn)$）