2020-08-21 16:52 已编辑门头沟学院 C++

关注

积性函数、狄利克雷卷积的一些结论

$T_0$
$\mu(n)$ 莫比乌斯函数， $\varphi(n)$ 欧拉函数， $u(n)=1$ ， $e(n)=n$ ， $I(n)=[n=1]$ ， $\sigma_k(n)=\sum_{d|n}d^k$ 。

$\omega (n)$ 为 $n$ 的不同素因子个数， $\Omega (n)$ 为 $n$ 的所有素因子个数。 $\lambda(n)=(-1)^{\Omega (n)}，G(a,b)为a,b最大公约数$ 。

$T_1$

$F=f\cdot u，f=F\cdot \mu$
$F(n)=\sum_{d|n}f(d)，f(n)=\sum_{d|n}F(d)\cdot \mu(\frac{n}{d})$
$F(d)=\sum_{d|n}f(n)，f(d)=\sum_{d|n}F(n)\cdot \mu(\frac{n}{d})$
$g为完全积性函数：$
$h=f\cdot g，f=h\cdot (g\mu)$
$h(n)=\sum_{d|n}f(d)\cdot g(\frac{n}{d})$
$f(n)=\sum_{d|n}h(d)\cdot g(\frac{n}{d})\cdot \mu(\frac{n}{d})$
图片说明

$T_2$

$I=u\cdot \mu，[n=1]=\sum_{d|n}\mu(d)，n=\sum_{d|n}\varphi(d)$
$1=\sum_{d|n}2^{\omega (d)}\cdot \lambda(\frac{n}{d})$
图片说明

$T_3$

$2^{\omega (n)}=\sum_{d|n}\mu(d)^2$
$=\sum_{d|n}[G(d,\frac{n}{d})=1]$
$=\sum_{d|n}\lambda(d)\cdot \mu(d)$
$=\sum_{d^2|n}\mu(d)\cdot \sigma _0(\frac{n}{d^2})$
$=\sum_{d|n}\sigma _0(d^2)\cdot \mu(\frac{n}{d})$

$\sum_{d|n^2}1=\sum_{d|n}2^{\omega (d)}$

$\mu(n)^2=\sum_{d^2|n}\mu(d)$
$=\sum_{d|n}2^{\omega (n)}\cdot \mu(\frac{n}{d})$
$=\mu(n)\cdot \lambda(n)$

$\lambda(n)=(-1)^{\Omega (n)}$
$=\sum_{d^2|n}\mu(\frac{n}{d^2})$
$=\sum_{d|n}\mu(d)\cdot \sigma_0(d)$

$\sum_{d|n}\lambda(d)=\left\{\begin{matrix} 1 & , &n=k^2 \\ 0 & , &n\neq k^2 \end{matrix}\right.$

$T_4$
$\varphi(mn)=G(m,n)\cdot \varphi(lcm(m,n))$
$\varphi(mn)\cdot \varphi(G(m,n))=G(m,n)\cdot \varphi(m)\cdot \varphi(n)$
$\varphi(lcm(m,n))\cdot \varphi(G(m,n))=\varphi(m)\cdot \varphi(n)$
$\varphi(n^m)=n^{m-1}\cdot \varphi(n)$
$\varphi(n\cdot 2^k)=\left\{\begin{matrix} \varphi(n)\cdot 2^k& , & n\; is\; even \\ \varphi(n)\cdot 2^{k-1} & , &n\; is\; odd \end{matrix}\right.$
$\mu(lcm(m,n))=\mu(m)\cdot \mu(n)\cdot \mu(G(m,n))$

$T_5$
$f积性函数$
$\sum_{d|n}\mu(d)\cdot f(d)=\prod_{p|n}(1-f(p))$
$\sum_{d|n}\mu(d)^2\cdot f(d)=\prod_{p|n}(1+f(p))$

$T_6$
$\sum_{i=1}^{n}[d|i^k]=\left \lfloor \frac{n}{f_k(d)}\right \rfloor$
$f_k(n)=\prod_{p^a||n}p^{\left \lceil \frac{a}{k}\right \rceil}$
$g(n)=(u^k)(n),g(p^a)=\binom{a+k-1}{a}，\sum_{i_1\cdot i_2\cdot ...\cdot i_k=n}f(i_1)\cdot ...\cdot f(i_k)，可用快速幂加速计算$
$G(a^m-1,a^n-1)=a^{G(m,n)}-1$
$若G(a,b)=1,则G(a^m-b^m,a^n-b^n)=a^{G(m,n)}-b^{G(m,n)}$

$T_7$
$\sum_{d|n}\sigma_0(d)^3=(\sum_{d|n}\sigma_0(d))^2$
$\sigma_0(i\cdot j)=\sum_{x|i}\sum_{y|j}[G(x,y)=1]$
$\sigma_1(i\cdot j)=\sum_{x|i}\sum_{y|j}(x\cdot \frac{j}{y})[G(x,y)=1]$
$g(n)=\sum_{i=1}^{n}\left \lceil \frac{n}{i}\right \rceil ，g(n)=g(n-1)+1+\sigma_0(n-1)$
$\sum_{i=1}^{n}\sum_{j=1}^{m}[p|i\cdot j]=\sum_{T|p}\left \lfloor \frac{n}{T}\right \rfloor\sum_{d|T}\left \lfloor \frac{m}{\frac{p}{d}}\right \rfloor\cdot \mu(\frac{T}{d})$
$\sum_{i=1}^{n}\sum_{j=1}^{n}[n|lcm(i,j)]=\sum_{d|n}\varphi(d)\cdot 2^{\omega (d)}$
$\sum_{i=1}^{n}\sum_{j=1}^{n}[n|i\cdot j]=\sum_{d|n}\varphi(d)\cdot \frac{n}{d}$

$T_8$
$\sum_{i=1}^{n}\sum_{j=1}^{m}f(G(i,j))=\sum_{T=1}^{n}\left \lfloor \frac{n}{T}\right \rfloor \cdot \left \lfloor \frac{m}{T}\right \rfloor \sum_{d|T}f(d)\cdot \mu(\frac{T}{d})$
$\sum_{i_1=1}^{n}...\sum_{i_k=1}^{n}f(G(i_1,..,i_k))=\sum_{T=1}^{n}\left \lfloor \frac{n}{T}\right \rfloor ^k \sum_{d|T}f(d)\cdot \mu(\frac{T}{d})$
$\sum_{d=1}^{n}f(d)\sum_{k=1}^{\frac{n}{d}}g(k)\cdot h(dk)=\sum_{T=1}^{n}h(T)\sum_{d|T}f(d)\cdot g(\frac{T}{d})$
$\sum_{d|n}f(d)\sum_{k|\frac{n}{d}}g(k)\cdot h(dk)=\sum_{T|n}h(T)\sum_{d|T}f(d)\cdot g(\frac{T}{d})$
$\sum_{i=1}^{n}\sum_{j=1}^{n}[G(i,j)=1]=(2\sum_{i=1}^{n}\varphi(i))-1$
$\sum_{i=1}^{n}\sum_{j=1}^{n}ij[G(i,j)=1]=\sum_{i=1}^{n}i^2\cdot \varphi(i)$