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

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

积性函数定义

满足$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}$$