莫比乌斯反演

by chainhelen

定义

定理:\(F(n)\)与\(f(n)\)是非负整数集合上的两个函数，并且满足\(F(n)=\sum_{d|n}^{} f(d)\)公式，那么就有$f(n)=\sum_{d|n}^{} \mu(d)F({n \over d})$ 上述函数\(\mu(d)\),就是莫比乌斯函数 定义如下:

  1. 若 \(d = 1\)，则 \(\mu(d) = 1\)
  2. 若 \(d = p_1p_2 \cdots p_k\), 其中 \(p_i\)互质，那么 \(\mu(d)=(-1)^{k}\)
  3. 其他情况下 \(\mu(d)=0\)

性质

  1. 对任意正整数\(n\)有:

    $\sum_{d|n} \mu(d) = \begin{cases} 1 & (n=1) \\

    0 & (n>1) \\

    \end{cases}$ 证明：

    (1)当\(n=1\)时显然

    (2)当\(n\neq1\)时，\(n\)分解可以得到\(n=p_{1}^{a_1}p_{2}^{a_2} \cdots p_{k}^{a_k}\)，故\(d\)的取值就是 \(d=p_1^{b_1}p_2^{b_2} \cdots p_k^{b_k} \quad 0 \le b_i \le a_i, i=1,2 \ldots k\)，可以得到 $\mu(d)=\mu(p_1^{b_1}p_2^{b_2} \cdots p_k^{b_k}) \quad 其中 0 \le b_i \le a_i, i=1,2 \ldots k$ 根据定义2、3看，\(b_i\)一定是0或1，\(\mu(d)\)才不等于０，现在我们对不为零的项求和. d包含r个质因子的项数为\({k \choose r}\)，那么根据性质２可以得到 $ \begin{align} \mu(d) &={k \choose 0} - {k \choose 1} + {k \choose 2} + \cdots +(-1)^k {k \choose k} \\ &= \sum_{i=0}^{k}(-1)^i{k \choose i} \\ &= \sum_{i=0}^{k}(-1)^i(1)^{k-i}{k \choose i} \\ &= (-1 + 1)^k \quad(二项式定理)\\ &= 0 \\ \end{align} $ 即证
  2. 对于任意正整数\(n\)有

    $\sum_{d|n}\frac{\mu(d)}{d}={\phi(n) \over n}$ 证明过程略，只要将\(F(n)=n，f(n)=\phi(n)\)带入，交叉相乘即可

证明

一开始，没太懂证明 $\sum_{d|n}^{} \mu(d)F({n \over d})=\sum_{d|n}\mu(d)\sum_{d'|{n \over d}}f({d'})=\sum_{d'|n}f(d')\sum_{d|{n \over d'}}\mu(d)=f(n)$

后来我举了了个例子，才明白写成下面方式会更懂点 $\sum_{d|n}^{} (\mu(d)*F({n \over d}))=\sum_{d|n}(\mu(d)*\sum_{d'|{n \over d}}f({d'})) = \sum_{d'|n}(f(d')*\sum_{d|{n \over d'}}\mu(d))=f(n)$

  1. 先看第二个等号是怎么过去的，假如求\(f(12)\)，公式如下：

    $f(12)=\sum_{d|12}^{} (\mu(d)*F({12 \over d}))$ 按照d的值可以将各项式拆成： $\begin{align} F(1) &= \mu(1)*f(1) +\mu(1)*f(2)+\mu(1)*f(4)+\mu(1)*f(6)+\mu(1)*f(12) \\

    F(2) &= \mu(2)*f(1) +\mu(2)*f(2)+\mu(2)*f(3)+\mu(2)*f(6) \\

    F(3) &= \mu(3)*f(1) +\mu(3)*f(2)+\mu(3)*f(4) \\

    F(4) &= \mu(4)*f(1) +\mu(4)*f(3) \\

    F(6) &= \mu(6)*f(1) +\mu(6)*f(2) \\

    F(12) &= \mu(12)*f(1)\\

    \end{align}$ 注意仔细看，例如能与f(2)相乘的有，\(\mu(1)，\mu(2)，\mu(3)，\mu(6)\).

    整个多项式中能与\(f(x)\)相乘的\(\mu(y)\). 可以观察到y值的范围，y 是取尽了\(x*y\le n\)并且\(y|n\). 所以对于含有\(f(d)\)的项就是 $\begin{align} f(x)*\sum_{y|{n \over x}}\mu({n \over x})

    \end{align}$ 而x取所有满足x|d的值，故上面第二个等式化简为， $\sum_{d|n}(\mu(d)*\sum_{d'|{n \over d}}f({d'})) = \sum_{d'|n}(f(d')*\sum_{d|{n \over d'}}\mu(d))$
  2. 再来看看等三个等号怎么过去的，前面已经有结论:\(\sum_{k|n} \mu(k) =

    \begin{cases} 1 & (n=1) \\

    0 & (n>1) \\

    \end{cases}\)，所以当且仅当\(n|d'\)等于１，即d'=n的时候\(\sum_{d|{n \over d'}}\mu(d)\)是１，其他时候都等于０.

    所以得到: $ \sum_{d'|n}(f(d')*\sum_{d|{n \over d'}}\mu(d))=f(n) $

入门实战

hdu1695　题目大致意思是变量\(x\)与\(y\)满足\(a \le x \le b\) ，\(c \le y \le d\)，（其中a = 1，c = 1，b、d未知），求有多少对\((x，y)\) 使得\(GCD(x，y) = k\)

解法:

  1. 很容易想到题目可以转化为满足，\(1 \le x \le {b \over k} \quad 1 \le y \le {d \over k}\)，（b、d未知），使得\(GCD(x，y) = 1\)的\((x，y)\) 对数

    设\(f(i)\)代表满足\(GCD(x，y) = i\)的\((x，y)\)对数，我们需要求的是\(f(1)\)

    则\(F(i)\)代表满足\(GCD(x，y) = i\)正整数倍数的\((x，y)\)对数，很容易知道\(F(i)=[{b \over k} / i] * [{d \over k} / i] \)

    记\(f(1)=M\)
  2. 当然按照题意需要去掉重复的，比如\((n_1，n_2)\)与\((n_2，n_1)\)

    仔细观察，重复的的\(x，y\)其实只在\( 1 \le x \le min({b \over k}, {d \over k}) \)与\( 1 \le y \le min({b \over k}, {d \over k}) \)中出现，那么可以利用\(F^{'}(i)=[min({b \over k}, {d \over k}) / i] * [min({b \over k}, {d \over k}) / i]\)，同理可得对数结果

    记\(f^{'}(1)=M^{'}\)

    对于\(f^{'}(１)\)来看，如果\(x \gt y\)的情况有\(n\)个，那么\(x \lt y\)的也有\(n\)个，另外还有\(x == y\)，有且仅有一个那就是\((1, 1)\) ，所以\(M^{'} = 2 * n + 1\)，只要结果M中去除掉\([M^{'} / 2] = [(2 * n + 1) / 2] = n\)
  3. \(\mu(i)\)是积性函数，本来按照定义就可以直接求出值，类似于筛法＋打表，提前记录出素数. 但是其实可以利用\(\sum_{d|n}\mu(d) = 0 \quad (当n != 1)\) . 按顺序求出\(\mu(i)\)，所以当求到\(\mu(n)\)的时候，

    只要将\(0 - \sum_{d|n \&\& d \neq n}\mu(d)\)即可，所以在求出\(\mu(n)\)之前，\(\mu(n)\)可以用来存储\(\sum_{d|n \&\& d \neq n}\mu(d)\)，并不断更新该值.
  4. 这道题有道坑，就是\(k\)可以为0
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;  
const int N = 1e5+5;  
int mu[N];  
void getMu(){  
    memset(mu, 0, sizeof(mu));
    for(int i = 1;i < N;i++) {
        int sum = i == 1 ? 1 : 0;
        mu[i] = sum - mu[i];
        for(int j = 2;j * i < N;j++) {
            mu[j * i] += mu[i];
        }
    }
}

int m, t;  
int a, b ,c , d, k;

int main() {  
    getMu();
    scanf("%d", &t);
    for(int ii = 1;ii <= t;ii++) {
        scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
        long long ans1 = 0;
        long long ans2 = 0 ;
        if(0 == k) {
            printf("Case %d: %lld\n", ii, 0LL);
            continue;
        }
        b /= k;
        d /= k;
        if(b > d) {
            swap(b, d);
        }
        for(int i = 1;i <= b;i++) {
            ans1 += (long long)mu[i] * (b / i) * (d / i);
        }
        for(int i = 1;i <= b;i++) {
            ans2 += (long long)mu[i] * (b / i) * (b / i);
        }
        printf("Case %d: %lld\n", ii, ans1 - ans2 / 2);
    }
    return 0;
}

未经同意，禁止转载

本文地址 http://blog.hacking.pub/2016/11/15/mo-bi-wu-si-fan-yan-2/

参考

吐槽

markdown + mathjax 因为转义把\(写成\\(之外，还有\sum_也要写成\sum\_，因为_会被markdown干掉，问题是如果一行之中只有一个\sum_的时候，使用\sum_没有问题的，出现两个就不行了