NanoApe's Blog

既是咸鱼又是辣鸡

【数论】积性函数、莫比乌斯反演、狄利克雷卷积

NanoApe posted @ 2016年1月02日 21:35 in 蒟蒻不撕烤智熵何来 , 1205 阅读

 

积性函数定义

满足$F(1)=1$且$F(ab)=F(a)F(b)$(ab互质)的函数F(n)为积性函数。

满足$F(1)=1$且$F(ab)=F(a)F(b)$的函数F(n)为完全积性函数。

 

积性函数线性筛

如同质数的线性筛

当x与p互质时$F(xp)=F(x)F(p)$

当x与p不互质时$F(xp)=F(x)G(p)$并Break掉

其中p为质数,G(n)为F(n)某对应函数(口胡

 

欧拉函数

定义:$\varphi(n)$表示1至n中与n互质的个数

$$\varphi(n) = \sum_{i=1}^{n} [gcd(i,n)=1]$$

$$\varphi(xp) = \begin{cases} \varphi(x)*\varphi(p) & gcd(x,p)=1 \\ \varphi(x)*p & gcd(x,p)>1 \\ \end{cases}$$

$$n={p_1}^{a_1}{p_2}^{a_2}{p_3}^{a_3}...$$

$$\varphi(n)=n{p_1-1 \over p_1}{p_2-1 \over p_2}{p_3-1 \over p_3}...=n \prod_{p|n}{p-1 \over p}$$

$$\sum_{d|n}\varphi(d)=n$$

⑤(由④通过莫比乌斯反演可得)

$$\varphi(n)=\sum_{d\mid n} d \cdot \mu(n/d)$$

⑥(欧拉定理)

$$a^{\varphi(m)} \equiv 1 \pmod m \; (gcd(a,m)=1且m\ge2)$$

⑦(费马小定理)

$$a^{\varphi(p)=p-1} \equiv 1 \pmod p$$

 

莫比乌斯函数

①(定义)

$$\mu (n) = \begin{cases} 1 & 若n=1 \\ (-1)^k & 若n无平方数因数且n=p_1p_2......p_k \\ 0 & 若n有大于1的平方数因数 \\ \end{cases}$$

$$\mu(xp) = \begin{cases} -\mu(x) & gcd(x,p)=1 \\ 0 & gcd(x,p)>1 \\ \end{cases}$$

$$\sum_{d|n} \mu(d) = \epsilon(n) = \begin{cases} 1 & 若n=1 \\ 0 & 其他状况 \end{cases}$$

$$\sum_{d|n}{\mu(d) \over d}={\varphi(n) \over n}$$

 

莫比乌斯反演

$$F(n)=\sum_{d|n}f(d) \quad \Rightarrow \quad f(n)=\sum_{d|n}\mu(\frac{n}{d})F(d)$$

$$F(n)=\sum_{n|d}f(d) \quad \Rightarrow \quad f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$$

证明:

$$\sum_{d|n}\mu(d)F(\frac nd)=\sum_{d|n}\mu(d)\sum_{d'|\frac nd}f(d')=\sum_{d'|n}f(d')\sum_{d|\frac {n}{d'}}\mu(d)=f(n)$$

 

常用推导公式

$$\sum_{a=1}^n \sum_{b=1}^m [gcd(a,b)=1]=\sum_d\mu(d)\frac nd\frac md$$

$$\sum_{a=1}^n \sum_{b=1}^m [gcd(a,b)=x]=\sum_{a=1}^{n/x} \sum_{b=1}^{m/x} [gcd(a,b)=1]=\sum_d\mu(d)\frac n{dx}\frac m{dx}$$

证明:设

$$f(d)=\sum_{a=1}^n \sum_{b=1}^m [gcd(a,b)=d]$$

$$F(d)=\sum_{a=1}^n \sum_{b=1}^m [d|gcd(a,b)]=\frac nd\frac md=\sum_{d|x}f(x)$$

由反演可得

$$f(x)=\sum_{x|d} \mu(\frac dx)F(d)=\sum_{x|d} \mu(\frac dx)\frac nd\frac md=\sum_d\mu(d)\frac n{dx}\frac m{dx}$$

$$\sum_{a=1}^n \sum_{b=1}^m gcd(a,b)=\sum_d \varphi(d)\frac nd \frac md$$

证明:

$$\begin{align} & \sum_{a=1}^n \sum_{b=1}^m gcd(a,b) \\ & =\sum_a \sum_b \sum_{d|gcd(a,b)} \varphi(d) \\ & =\sum_d \varphi(d)\frac nd \frac md \end{align}$$

 

其余积性函数

①(对于狄利克雷卷积的乘法单位)

$$\epsilon(n)= \begin{cases} 1 & 若n=1 \\ 0 & 其他状况 \end{cases}$$

②(与某固定数k的最大公因数$gcd(k,x)$)

③(除数函数$\sigma_k(n)$,n的所有正因数的k次幂之和)

$\sigma_0(n)$为n的正因数个数

$\sigma_1(n)$为n的正因数之和

$$\sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} = \prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}$$

 

狄利克雷卷积

对于函数$f(x)g(x)$,定义其狄利克雷卷积为$(f*g)(n)=\sum_{d|n}f(d)g(\frac{n}{d})$

其满足交换、结合、分配率

$\epsilon(n)$为单位函数,满足$f=f*\epsilon=\epsilon*f$

对于任意函数$f(x)$,若$f(1)\not=0$,都有唯一的逆函数$f^{-1}$,使得$f*f^{-1}=\epsilon$

 

 

 

 

$$g(n)=\sum_{p|n}\mu(\frac np)$$

$$g(xp) = \begin{cases} \mu(x)-g(x) & gcd(x,p)=1 \\ \mu(x) & gcd(x,p)>1 \\ \end{cases}$$

 

 

 

 

 

PS 网上有关的资料

http://blog.csdn.net/acdreamers/article/details/8542292

http://blog.csdn.net/acdreamers/article/details/24011127

http://blog.csdn.net/acdreamers/article/details/24023235


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter