专栏文章

数论函数

aaaaaaaqqqqqq
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqg4vvw
此快照首次捕获于
2025/12/04 04:15
3 个月前
此快照最后确认于
2025/12/04 04:15
3 个月前
查看原文
  • 数论函数：定义域在正整数的函数。
  • 积性函数：对于 gcd⁡(x,y)=1\gcd(x, y) = 1，有 f(xy)=f(x)f(y)f(xy) = f(x)f(y) 的数论函数 ff 。
  • 完全积性函数：不管互不互质都满足上面那个柿子的数论函数。
  • 常用的数论函数运算符号
    • (f⋅g)(x)=f(x)g(x)(f \cdot g)(x) = f(x)g(x)
    • (f∘g)(x)=f(g(x))(f \circ g)(x) = f(g(x))
    • (f∗g)(x)=∑d∣xf(d)g(xd)(f * g)(x) = \sum_{d | x}f(d)g(\frac{x}{d}) （Dirichlet 卷积）
  • 积性函数在这些运算中保持其积性。
  • 函数运算中的一些法则
    • 卷积单位元 ε\varepsilon ：ε(x)=[x=1]\varepsilon(x) = [x = 1] 。你会发现 f∗ε=ff * \varepsilon = f 。
    • 常数函数 c(x)=1c(x) = 1 。把它拿来和 ff 卷积相当于 Dirichlet 前缀和。(f∗1)(x)=∑d∣xf(d)(f * 1)(x) = \sum_{d | x} f(d) 。
    • 所有 f(1)≠0f(1) \neq 0 的数论函数都存在 唯一的 卷积逆元。具体地我们可以去解方程，得到一个
      f−1(x)=ε(x)−∑d∣x,d≠1f(d)f−1(xd)f(1)f^{-1}(x) = \frac{\varepsilon(x) - \sum_{d | x, d \neq 1}f(d)f^{-1}(\frac{x}{d})}{f(1)}。
    • 特别地，对于积性函数，
      f(1)=f−1(1)=1,f−1(x≥2)=−sumd∣x,d∣1f(d)f−1(xd)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(nn)O(n \sqrt n) 或 O(nlog⁡n)O(n \log n) 。
    • 高维前缀和 ，每个质数为一维。O(nlog⁡log⁡n)O(n \log \log n) 。
  • Mobius 函数
    • 其实就是 1(x)1(x) 的逆元。
    • 想想一个数在做了 Dirichlet 前缀和之后怎么还原。
    • 对了，一步一步退回去，就是高维差分。
    • Mobius 函数在 Dirichlet 卷积里的本质就是高维差分。记每个质因数为一维。
    • 定义：
      μ(x)={1x=1(−1)kx=p1p2…pk,p∈Prime0p2∣x,p∈Prime\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}
      我们将 ff 与它进行卷积。
      (f∗μ)(x)=∑d∣xf(d)μ(xd)(f * \mu)(x) = \sum_{d | x} f(d) \mu(\frac{x}{d})
      我们可以发现 μ\mu 在这里就是一个容斥系数。每一维最多增加 11 ，这就是为什么遇到平方项直接赋值为 00 。ff 与 μ\mu 卷积相当于完成了一次以质因数为维度的高维差分操作。
  • Mobius 反演
    ∑d∣xμ(x)={1x=10x≠1\sum_{d | x} \mu(x) = \begin{cases} 1 & x = 1 \\ 0 & x \ne 1 \end{cases}
    把 xx 质因数分解之后用组合数枚举 dd ，展开组合数就能得到这个结果了。
    常见的套路是用来处理 gcd 。所以有
    [gcd⁡(x,y)=1]=∑d∣gcd⁡(x,y)μ(d)[\gcd(x, y) = 1] = \sum_{d | \gcd(x, y)} \mu(d)
    这个很显然。
    然后就是推广一下
    [gcd⁡(x,y)=k]=∑d∣gcd⁡(xk,yk)μ(d)[\gcd(x, y) = k] = \sum_{d | \gcd(\frac{x}{k}, \frac{y}{k})} \mu(d)
    注意这里先要保证整除。这个技巧常和整除分块连用。
    然后就是利用它高维前缀和的意义。
    前缀和反演：
    F(x)=∑d∣xf(d)F(x) = \sum_{d | x} f(d)
    （卷上 11）
    则
    f(x)=∑d∣xμ(xd)F(d)f(x) = \sum_{d | x} \mu(\frac xd) F(d)
    相当于做了一次高维差分，像我们前面说的那样。
    后缀和反演：
    F(x)=∑x∣df(d)F(x) = \sum_{x | d} f(d)
    则
    f(x)=∑x∣dμ(dx)F(d)f(x) = \sum_{x | d} \mu(\frac dx) F(d)
    相当于反着来。
    id\text{id} 卷上 μ\mu 得到 φ\varphi 。
    φ\varphi 卷上 11 得到 id\text{id} 。
    这两个运算是对称的，下面那个就是欧拉反演。
    当我们直接计算 ff 比较困难时（比如说要求 gcd 恰好等于某个值），考虑构造好算的 FF （比如两数的公因数有这个就行），然后反演。
    如果我们要算 gcd⁡(i,j)\gcd(i, j) ，考虑用一个很弱智的反演
    ∑i=1di[gcd⁡(i,j)=i]\sum_{i = 1} ^ d i [\gcd(i, j) = i]
    把它转化为判定性问题。
  • 常见的积性函数乘积展开
    赛场上推不出来的那种。我们不生产结论，我们只是 OI-wiki 的搬运工。
    μ(ij)=μ(i)μ(j)[gcd⁡(i,j)=1]\mu(ij) = \mu(i)\mu(j)[\gcd(i, j) = 1] φ(ij)=φ(i)φ(j)gcd⁡(i,j)φ(gcd⁡(i,j))\varphi(ij) = \frac{\varphi(i)\varphi(j)\gcd(i, j)}{\varphi(\gcd(i, j))} d(ij)=∑x∣i∑y∣j[gcd⁡(x,y)=1]d(ij) = \sum_{x | i} \sum_{y | j} [\gcd(x, y) = 1]
    （前面两个还好，第三个我是真不知道怎么整出来的。）

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...