Warning: session_start(): open(/tmp/sess_88698af8c01b8d73c47ce72a78eb33de, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 莫比乌斯反演 ====== ===== 简介 ===== 莫比乌斯反演是数论中的重要内容. 对于一些函数 $f(n)$, 如果很难直接求出它的值, 而容易求出其倍数和或约数和 $g(n)$, 那么可以通过莫比乌斯反演简化运算, 求得 $f(n)$ 的值 开始学习莫比乌斯反演前, 我们需要一些前置知识: 积性函数、Dirichlet 卷积、莫比乌斯函数. ===== 前置知识 ===== === 引理 1 === $$ \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 $$ === 引理 2 === $$ \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 $$ $|V|$ 表示集合 $V$ 的元素个数 ===== 数论分块 ===== 数论分块的过程大致如下: 考虑含有 $\left\lfloor\frac{n}{i}\right\rfloor$ 的求和式子 ( $n$ 为常数) 对于任意一个 $i$ ( $i\le n$ ), 我们需要找到一个最大的 $j$ ( $i\le j\le n$ ), 使得 $\left\lfloor\frac{n}{i}\right\rfloor=\left\lfloor\frac{n}{j}\right\rfloor$. 而 $j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor$. 利用上述结论, 我们每次以 $[i,j]$ 为一块, 分块求和即可 ===== 积性函数 ===== === 定义 === 若 $gcd(x,y)=1$ 且 $f(xy)=f(x)f(y)$, 则 $f(n)$ 为积性函数. === 性质 === 若 $f(x)$ 和 $g(x)$ 均为积性函数, 则以下函数也为积性函数: $$ h(x)=f(x^p)\\ h(x)=f^p(x)\\ h(x)=f(x)g(x)\\ h(x)=\sum_{d|x}f(d)g(\frac x d) $$ === 例子 === 单位函数: $\varepsilon(n)=[n=1]$ 恒等函数: $id_k(n)=n^k, id_1(n)$ 通常简记为 $id(n)$ 常数函数: $1(n)=1$ 除数函数: $\sigma_k(n)=\sum_{d|n}d^k$, $\sigma_0(n)$ 通常简记作 $d(n)$ 或 $\tau(n)$, $\sigma_1(n)$ 通常简记作 $\sigma(n)$ 欧拉函数: $\varphi(n)=\sum_{i=1}^n[gcd(i,n)=1]$ 莫比乌斯函数: $\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 卷积 ===== === 定义 === 定义两个数论函数 $f,g$ 的 $Dirichlet$ 卷积为 $$ (f*g)(n)=\sum_{d|n}f(d)g(\frac n d) $$ === 性质 === $Dirichlet$ 卷积满足交换律和结合律 其中 $\varepsilon$ 为 $Dirichlet$ 卷积的单位元 (任何函数卷 $\varepsilon$ 都为其本身) === 例子 === $$ \varepsilon=\mu*1\Longleftrightarrow\varepsilon(n)=\sum_{d|n}\mu(d)\\ d=1*1\Longleftrightarrow d(n)=\sum_{d|n}\\ \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) $$ ===== 莫比乌斯函数 ===== === 定义 === $\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}) $$