卷积与莫比乌斯反演

Part 1 卷积

卷积是一种由两个函数生成第三个函数的操作，定义如下：

\[ h(x) = \sum_{d|x} f(d)g(\frac{x}{d} ) = \sum_{ab = x} f(a)g(a) \]

就是枚举 x 的每对因数，计算 f, g 填入他们的和。

一般记为 \(h = f \ast g\)

卷积满足交换律，结合率，分配律，且 \(f = g\) 的充要条件是 \(f \ast h = g \ast h\) 且 \(h(1) \neq 1\)

Part 1.1 几个常见的积性函数

$ (x) = [x = 1] $ 单位函数 ($ [p] $ 的意思是当 p 为 true 时等式为 0 ，否则为 0)

$ I(x) = 1 $ 常数函数

$ (x) $ 莫比乌斯函数

$ (x) $ 欧拉函数

有以下结论：

\[ \begin{matrix} \epsilon = 1 \ast \mu\\1 = \epsilon \ast 1 \end{matrix} \]

Part 2 莫比乌斯反演

定义：若 \[ g(n) = \sum_{d \mid n} f(d) \] 则有 \[ f(n) = \sum_{d \mid n} g(d) \mu(\frac{n}{d}) \]

其实可以理解成 \[ g = f \ast 1 \leftrightarrow f = g \ast \mu \]

很多时候，可以用到这个推论 \[ \mu \ast 1 = \epsilon \] 即 \[ \sum_{d \mid n} \mu(d) = \epsilon(n) = [n = 1] \]

如果我们能够转化式子，我们就能用下面的方式线性预处理莫比乌斯以及其它积性函数。(线性筛)

void getMu() {
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!flg[i]) p[++tot] = i, mu[i] = -1;
    for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
}

如果没看懂，没关系，推一道题就行了。