莫比乌斯反演学习笔记

莫比乌斯函数

定义

定义函数 \mu (d)

还有一些常用的性质

1.最常用的: \forall n \in \N, \sum_{d|n} \mu(d) = [n=1].

2.\forall n \in \N, \sum_{d|n} \frac{\mu (d)}{d} = \frac{\varphi (n)}{d}

均不会证

Code

inline void getMu()
{
    int siz = 10000000;
    isPrime[1] = mu[1] = 1;
    for (register int i = 2; i <= siz; ++ i) {
        if (!isPrime[i]) {
            prime[++ tot] = i, mu[i] = -1;
        }
        for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) {
            isPrime[i * prime[j]] = 1;
            if (i % prime[j]) mu[i * prime[j]] = -mu[i];
            else {
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
}

莫比乌斯反演

定理

设两个单元函数 F(x) , f(x) 分别为

F(x) = \sum_{d\mid n} f(d)

那么

f(x) = \sum_{d|n} \mu(d) F(\lfloor \frac{n}{d} \rfloor)

Summary

其实你根本不需要会这个反演,只需要知道上面那个最常用的性质就可以了

做几个题就会了