2020-2021:teams:legal_string:莫比乌斯反演_lgwza
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:莫比乌斯反演_lgwza [2020/07/03 22:34] lgwza 创建 |
2020-2021:teams:legal_string:莫比乌斯反演_lgwza [2020/07/03 22:38] (当前版本) lgwza [积性函数] |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| $$ | $$ | ||
| - | \forall a,b,c\in\Z,\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor | + | \forall a,b,c\in Z,\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor |
| $$ | $$ | ||
| 行 18: | 行 18: | ||
| $$ | $$ | ||
| - | \forall n\in\N,\left|\left\{\left\lfloor\frac{n}{d}\right\rfloor|d\in\N\right\}\right|\le\left\lfloor2\sqrt{n}\right\rfloor | + | \forall n\in N,\left|\left\{\left\lfloor\frac{n}{d}\right\rfloor|d\in N\right\}\right|\le\left\lfloor2\sqrt{n}\right\rfloor |
| $$ | $$ | ||
| 行 60: | 行 60: | ||
| 欧拉函数: $\varphi(n)=\sum_{i=1}^n[gcd(i,n)=1]$ | 欧拉函数: $\varphi(n)=\sum_{i=1}^n[gcd(i,n)=1]$ | ||
| - | 莫比乌斯函数: $\mu(n)=\left\{\begin{array}{}1\qquad\qquad\quad n=1\\0\qquad\qquad\quad \exist d>1:d^2|n\\(-1)^{\omega(n)}\qquad otherwise\end{array}\right.$ 其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数, 是一个积性函数 | + | 莫比乌斯函数: $\mu(n)=\left\{\begin{array}{}1&n=1\\0&存在 d>1:d^2|n\\(-1)^{\omega(n)}&otherwise\end{array}\right.$ 其中 $\omega(n)$ 表示 $n$ 的本质不同质因子个数, 是一个积性函数 |
| ===== Dirichlet 卷积 ===== | ===== Dirichlet 卷积 ===== | ||
| 行 83: | 行 83: | ||
| \sigma=id*1\Longleftrightarrow\sigma(n)=\sum_{d|n}d\\ | \sigma=id*1\Longleftrightarrow\sigma(n)=\sum_{d|n}d\\ | ||
| \varphi=\mu*id\Longleftrightarrow\varphi(n)=\sum_{d|n}d\cdot\mu(\frac n d) | \varphi=\mu*id\Longleftrightarrow\varphi(n)=\sum_{d|n}d\cdot\mu(\frac n d) | ||
| + | $$ | ||
| + | |||
| + | ===== 莫比乌斯函数 ===== | ||
| + | |||
| + | === 定义 === | ||
| + | |||
| + | $\mu$ 为莫比乌斯函数, 定义为 $$ | ||
| + | \mu(n)=\left\{ | ||
| + | \begin{array}{l} | ||
| + | 1&n=1\\ | ||
| + | 0&n含有平方因子\\ | ||
| + | (-1)^k&k为n的本质不同质因子个数 | ||
| + | \end{array}\right. | ||
| + | $$ 详细解释一下: | ||
| + | |||
| + | 令 $n=\prod_{i=1}^kp_i^{c_i}$, 其中 $p_i$ 为质因子, $c_i\ge1$. 上述定义表示: | ||
| + | |||
| + | - $n=1$ 时, $\mu(n)=1$; | ||
| + | - 对于 $n\ne1$ 时: | ||
| + | - 当存在 $i\in[1,k]$, 使得 $c_i>1$ 时, $\mu(n)=0$, 也就是说只要某个质因子出现的次数超过一次, $\mu(n)$ 就等于 $0$; | ||
| + | - 当任意 $i\in[1,k]$, 都有 $c_i=1$ 时, $\mu(n)=(-1)^k$, 也就是说每个质因子都仅仅只出现过一次时, 即 $n=\prod_{i=1}^kp_i$, $\{p_i\}_{i=1}^k$ 中各元素唯一时, $\mu(n)$ 等于 $-1$ 的 $k$ 次幂, 此处 $k$ 指的便是仅仅只出现过一次的质因子的总个数. | ||
| + | |||
| + | === 性质 === | ||
| + | |||
| + | 莫比乌斯函数不但是积性函数, 还有如下性质: $$ | ||
| + | \sum_{d|n}\mu(d)=\left\{ | ||
| + | \begin{array}{l} | ||
| + | 1&n=1\\ | ||
| + | 0&n\ne1 | ||
| + | \end{array}\right. | ||
| + | $$ 即 $\sum_{d|n}\mu(d)=\varepsilon(n)$, 即 $\mu*1=\varepsilon$ $$ | ||
| + | [gcd(i,j)=1]\Longleftrightarrow\sum_{d|gcd(i,j)}\mu(d) | ||
| + | $$ | ||
| + | |||
| + | $$ | ||
| + | \varphi*1=ID | ||
| + | $$ | ||
| + | |||
| + | ( $ID$ 函数即 $f(x)=x$ ) | ||
| + | |||
| + | 该式子两侧同时卷 $\mu$ 可得 $\varphi(n)=\sum_{d|n}d\cdot\mu(\frac{n}{d})$ | ||
| + | |||
| + | ===== 莫比乌斯反演 ===== | ||
| + | |||
| + | === 公式 === | ||
| + | |||
| + | 设 $f(n),g(n)$ 为两个数论函数 | ||
| + | |||
| + | 如果有 $$ | ||
| + | f(n)=\sum_{d|n}g(d) | ||
| + | $$ 那么有 $$ | ||
| + | g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d}) | ||
| $$ | $$ | ||
2020-2021/teams/legal_string/莫比乌斯反演_lgwza.1593786879.txt.gz · 最后更改: 2020/07/03 22:34 由 lgwza
