狄利克雷卷积

What · 是什么

数论函数 f,g 的 Dirichlet 卷积定义为 (f*g)(n)=Σ_{d|n} f(d)g(n/d)，对 n 的所有正因子求和。它在数论函数全体上构成交换环（Dirichlet 环），单位元为 ε(n)=[n=1]（Iverson 括号）。关键恒等式：ε=μ*1（莫比乌斯反演之基）、τ=1*1（因子数）、σ=id*1（因子和）、φ=id*μ（欧拉函数）、id=φ*1。积性函数对卷积封闭；完全积性函数 f 的卷积逆为 μf。应用：莫比乌斯反演、杜教筛、狄利克雷前缀和/差分、积性函数求和，是数论算法（尤其是 O(n^{2/3}) 级数论求和）的理论核心。

Why · 为什么

How · 实现

伪代码

# 暴力卷积 O(n log n)
def dirichlet_conv(f, g, n):
  h = [0]*(n+1)
  for d in range(1, n+1):
    for k in range(1, n//d + 1):
      h[d*k] += f[d] * g[k]
  return h

# 莫比乌斯反演: g = f*1  =>  f = g*μ
# 杜教筛: S(n) = Σ_{i<=n} h(i), h = f*g, 选好 g 使前缀和可求

Python 实现

def conv_naive(f, g, n):
    """Dirichlet 卷积 (f*g)(1..n). f,g 为长度 n+1 的列表(索引从1开始)."""
    h = [0] * (n + 1)
    for d in range(1, n + 1):
        fd = f[d]
        if fd == 0:
            continue
        for k in range(1, n // d + 1):
            h[d * k] += fd * g[k]
    return h


def mobius(n):
    """莫比乌斯函数表 mu[1..n] (线性筛)."""
    mu = [0] * (n + 1)
    mu[1] = 1
    primes = []
    is_comp = [False] * (n + 1)
    for i in range(2, n + 1):
        if not is_comp[i]:
            primes.append(i)
            mu[i] = -1
        for p in primes:
            if i * p > n:
                break
            is_comp[i * p] = True
            if i % p == 0:
                mu[i * p] = 0
                break
            mu[i * p] = -mu[i]
    return mu


def conv_with_mu(f, n):
    """f*mu: 莫比乌斯反演的一步."""
    return conv_naive(f, mobius(n), n)


def conv_with_one(f, n):
    """f*1: 前缀和型卷积 (Dirichlet 前缀和)."""
    h = f[:]
    primes = [i for i in range(2, n + 1) if mobius(i) != 0 or i == 2]
    # 用线性筛质数
    comp = [False] * (n + 1)
    pr = []
    for i in range(2, n + 1):
        if not comp[i]:
            pr.append(i)
        for p in pr:
            if i * p > n:
                break
            comp[i * p] = True
            if i % p == 0:
                break
    for p in pr:
        for k in range(1, n // p + 1):
            h[k * p] += h[k]
    return h


def divisor_count_from_conv(n):
    """用 tau=1*1 验证: tau(k)=因子个数."""
    one = [0] + [1] * n
    tau = conv_naive(one, one, n)
    return tau


if __name__ == "__main__":
    N = 30
    # tau = 1*1
    one = [0] + [1] * N
    tau = conv_naive(one, one, N)
    for k in range(1, N + 1):
        cnt = sum(1 for d in range(1, k + 1) if k % d == 0)
        assert tau[k] == cnt, k

    # epsilon = mu*1
    mu = mobius(N)
    eps = conv_naive(mu, one, N)
    for k in range(1, N + 1):
        assert eps[k] == (1 if k == 1 else 0), k

    # sigma = id*1
    ids = [0] + list(range(1, N + 1))
    sig = conv_naive(ids, one, N)
    for k in range(1, N + 1):
        s = sum(d for d in range(1, k + 1) if k % d == 0)
        assert sig[k] == s, k

    # phi = id*mu
    phi = conv_naive(ids, mu, N)
    for k in range(1, N + 1):
        assert phi[k] == sum(1 for i in range(1, k + 1) if __import__('math').gcd(i, k) == 1), k

    # id = phi*1 (反向验证)
    id_back = conv_naive(phi, one, N)
    for k in range(1, N + 1):
        assert id_back[k] == k

    # 结合律: (1*1)*mu == 1*(1*mu) == 1*eps == 1
    t1 = conv_naive(conv_naive(one, one, N), mu, N)
    for k in range(1, N + 1):
        assert t1[k] == one[k]
    print("All tests passed.")

易错点

• 卷积求和范围是 d|n，不是 d≤n 全枚举（暴力时要按倍数累加）
• 积性函数卷积仍积性，但完全积性卷积不保证完全积性
• ε(n)=[n=1]，单位元别和常数函数 1 混淆
• 莫比乌斯反演符号方向：g=f*1 ⇔ f=g*μ（μ 是 1 的逆）
• 线性筛 μ 时 i%p==0 要置 mu[i*p]=0 并 break，否则数组错位
• 杜教筛选择 g 时若 f*g 不是易求的常见函数会卡死

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/number-theory/dirichlet/
• OI Wiki✓ https://oi-wiki.org/math/number-theory/mobius/