数论函数

aaaaaaqqqqqq · 2025-01-20 18:30:23 · 算法·理论

• 数论函数：定义域在正整数的函数。

• 积性函数：对于 \gcd(x, y) = 1，有 f(xy) = f(x)f(y) 的数论函数 f 。

• 完全积性函数：不管互不互质都满足上面那个柿子的数论函数。

• 常用的数论函数运算符号

  • (f \cdot g)(x) = f(x)g(x)
  • (f \circ g)(x) = f(g(x))

• 积性函数在这些运算中保持其积性。

• 函数运算中的一些法则

  • 卷积单位元 \varepsilon ：\varepsilon(x) = [x = 1] 。你会发现 f * \varepsilon = f 。
  • 常数函数 c(x) = 1 。把它拿来和 f 卷积相当于 Dirichlet 前缀和。(f * 1)(x) = \sum_{d | x} f(d) 。
  • 所有 f(1) \neq 0 的数论函数都存在 唯一的 卷积逆元。具体地我们可以去解方程，得到一个
  - 特别地，对于积性函数， $$f(1) = f^{-1}(1) = 1, f^{-1}(x \ge 2) = -sum_{d | x, d | 1}f(d)f^{-1}(\frac{x}{d})$$ 。

• 求解 Dirichlet 前缀和

  • 可以枚举因数或者对于每个数枚举倍数，O(n \sqrt n) 或 O(n \log n) 。
  • 高维前缀和 ，每个质数为一维。O(n \log \log n) 。

• Mobius 函数

  • 其实就是 1(x) 的逆元。
  • 想想一个数在做了 Dirichlet 前缀和之后怎么还原。
  • 对了，一步一步退回去，就是高维差分。
  • Mobius 函数在 Dirichlet 卷积里的本质就是高维差分。记每个质因数为一维。
  • 定义： \mu(x) = \begin{cases} 1 & x = 1 \\ (-1)^k & x = p_1p_2\dots p_k , p \in \text{Prime} \\ 0 & p^2 | x, p \in \text{Prime} \end{cases}

  我们将 f 与它进行卷积。

  (f * \mu)(x) = \sum_{d | x} f(d) \mu(\frac{x}{d})

  我们可以发现 \mu 在这里就是一个容斥系数。每一维最多增加 1 ，这就是为什么遇到平方项直接赋值为 0 。f 与 \mu 卷积相当于完成了一次以质因数为维度的高维差分操作。

• Mobius 反演

  \sum_{d | x} \mu(x) = \begin{cases} 1 & x = 1 \\ 0 & x \ne 1 \end{cases}

  把 x 质因数分解之后用组合数枚举 d ，展开组合数就能得到这个结果了。

  常见的套路是用来处理 gcd 。所以有

  [\gcd(x, y) = 1] = \sum_{d | \gcd(x, y)} \mu(d)

  这个很显然。

  然后就是推广一下

  [\gcd(x, y) = k] = \sum_{d | \gcd(\frac{x}{k}, \frac{y}{k})} \mu(d)

  注意这里先要保证整除。这个技巧常和整除分块连用。

  然后就是利用它高维前缀和的意义。

  前缀和反演：

  F(x) = \sum_{d | x} f(d)

  （卷上 1）

  则

  f(x) = \sum_{d | x} \mu(\frac xd) F(d)

  相当于做了一次高维差分，像我们前面说的那样。

  后缀和反演：

  F(x) = \sum_{x | d} f(d)

  则

  f(x) = \sum_{x | d} \mu(\frac dx) F(d)

  相当于反着来。

  $\varphi$ 卷上 $1$ 得到 $\text{id}$ 。 这两个运算是对称的，下面那个就是欧拉反演。 当我们直接计算 $f$ 比较困难时（比如说要求 gcd 恰好等于某个值），考虑构造好算的 $F$ （比如两数的公因数有这个就行），然后反演。 如果我们要算 $\gcd(i, j)$ ，考虑用一个很弱智的反演 $$ \sum_{i = 1} ^ d i [\gcd(i, j) = i] $$ 把它转化为判定性问题。

• 常见的积性函数乘积展开

  赛场上推不出来的那种。我们不生产结论，我们只是 OI-wiki 的搬运工。

  \mu(ij) = \mu(i)\mu(j)[\gcd(i, j) = 1] \varphi(ij) = \frac{\varphi(i)\varphi(j)\gcd(i, j)}{\varphi(\gcd(i, j))} d(ij) = \sum_{x | i} \sum_{y | j} [\gcd(x, y) = 1]

  （前面两个还好，第三个我是真不知道怎么整出来的。）