数论函数
常见的积性函数：
单位函数：$e(n)=[n=1]$
欧拉函数：$\varphi (n)=\sum_{i=1}^{n}[gcd(i,n)=1]=n\prod_{i=1}^{k}(1-\frac{1}{p_{i}})$
幂函数：$Id_{a}(n)=n^{a}$
除数函数：$\sigma (n)=\sum_{d|n}^{n}d$
莫比乌斯函数：$\mu (n)=[max(c_{1},c_{2}...c_{k})\leq 1](-1)^{k}$
------------
$Dirichlet$卷积
$h(n)=(f*g)(n)=\sum_{i|n}f(i)g(\frac{n}{i})$
$Dirichlet$卷积
$h(n)=(f*g)(n)=\sum_{i|n}f(i)g(\frac{n}{i})$
对于任意的$f\neq 0$，存在$g*f=e$
$g(n)=\frac{1}{f(1)}([n=1]-\sum_{i|n,i\neq1}g(\frac{n}{i}) )$
性质：
卷积乘满足乘法交换律，结合律，分配律
两个积性函数的卷积是积性函数
一个积性函数的逆也是积性函数
$e=\mu*1$
$Id=\varphi*1$
------------
反演：
反演：
已知$g(n)=\sum_{i|n}f(i)$，求$f(n)$：$f(n)=\sum_{i|n}g(i)\mu(\frac{n}{i})$
已知$g(n)=\sum_{n|d}f(d)$，求$f(n)$：$f(n)=\sum_{n|d}g(d)\mu(\frac{d}{n})$
------------
经典的套路
经典的套路
1.枚举gcd的取值
2.交换倍数和约数
3.用莫比乌斯函数求和替换$[a=1]$这类表达式
4.改写求和指标
3.用莫比乌斯函数求和替换$[a=1]$这类表达式
4.改写求和指标
5.整除分块
6.已知$f(n)$，求$g=f*1$
对$n$质因子分解，$n=\prod_{i=1}^{cnt}p_{i}^{c_{i}}$，则：
$g(n)=\prod_{i=1}^{cnt}\sum_{j=0}^{c_{i}}f(p_{i}^{j})$
7.现在有积性函数$f(n)$，设$n<m$，则：
$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))$
$=\sum_{i=1}^{d}f(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]$
$=\sum_{i=1}^{d}f(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{p|i,p|j}\mu (p)$
$=\sum_{i=1}^{d}f(d)\sum_{p=1}^{\frac{n}{d}}\mu (p)\left \lfloor \frac{n}{pd} \right \rfloor\left \lfloor \frac{m}{pd} \right \rfloor$
$=\sum_{D=1}^{n}\sum_{d|D}f(d)\mu (\frac{D}{d})\left \lfloor \frac{n}{D} \right \rfloor\left \lfloor \frac{m}{D} \right \rfloor$
------------
杜教筛
杜教筛
给定 $f(n)$，求 $s(n)=\sum_{i=1}^{n}f(i)$
考虑构造积性函数$h,g$，满足 $h=f*g$且 $h$ 的前缀和易求
$\sum_{i=1}^{n}h(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})$
$=\sum_{i=1}^{n}g(i)\sum_{j=1}^{\frac{n}{i}}f(j)$
$=\sum_{i=1}^{n}g(i)s(\frac{n}{i})$
$=g(1)s(n)+\sum_{i=2}^{n}g(i)s(\frac{n}{i})$
$\therefore g(1)s(n)=\sum_{i=1}^{n}h(i)-\sum_{i=2}^{n}g(i)s(\frac{n}{i})$
可以证明，复杂度为$O(n^\frac{2}{3})$
------------
关于杜教筛一些简单的套路
$s(n)=\sum_{i=1}^{n} \varphi (i)\Rightarrow \frac{n*(n+1)}{2}-\sum_{d=2}^{n}s(\frac{n}{d})$
$s(n)=\sum_{i=1}^{n} \mu (i)\Rightarrow 1-\sum_{d=2}^{n}s(\frac{n}{d})$
$s(n)=\sum_{i=1}^{n} i \varphi (i)\Rightarrow \frac{n*(n+1)(2n+1)}{6}-\sum_{d=2}^{n}s(\frac{n}{d})d$
(考虑构造 $h=\sum_{d|n}( d \varphi (d) )\frac{n}{d}=n\sum_{d|n}\varphi (d)=n^{2}$)
------------
