用狄利克雷前缀和卡常

August_Light · 2024-01-29 10:44:32 · 个人记录

符号：* 是狄利克雷卷积，1(n) := 1，\text{Id}(n) := n。

在一些数论题目中，线性筛并不是时间复杂度的瓶颈，但是线性筛筛积性函数时可能会带来较大的常数。

用狄利克雷前缀和可以卡常（时间复杂度 O(n \log \log n)）：

先预先线性筛或埃氏筛筛出 n 以内的所有质数。

    // primes 是一个 vector

    // 欧拉函数
    for (int i = 1; i <= n; i++)
        phi[i] = i;
    for (auto j : primes)
        for (int i = n / j; i >= 1; i--)
            phi[i * j] -= phi[i];
    // 莫比乌斯函数
    for (int i = 1; i <= n; i++)
        mu[i] = (i == 1);
    for (auto j : primes)
        for (int i = n / j; i >= 1; i--)
            mu[i * j] -= mu[i];
    // 约数个数函数
    for (int i = 1; i <= n; i++)
        d[i] = 1;
    for (auto j : primes)
        for (int i = 1; i * j <= n; i++)
            d[i * j] += d[i];

前提条件：这个函数 f 必须能表示成 g * 1 或 g * \mu，其中 g 是一个极其易于求值的函数。

例：\varphi = \text{Id} * \mu，\mu = \varepsilon * \mu，d = 1 * 1。