浅淡杜教筛

2023-10-11 14:03:46

浅淡杜教筛

狄利克雷卷积

本文的 * 均表示狄利克雷卷积

定义函数 \(f\) 与 \(g\) 狄利克雷卷积后函数的第 \(n\) 项为 \((f*g)(n) = \sum_{d|n}f(d)g(\frac nd)\)

积性函数

如果对于互质的两数 \(p, q\) 有：\(f(p)f(q) = f(pq)\) ，则认为函数 \(f\) 为积性函数

特别地，如果对于任意两数 \(p,q\) 有：\(f(p)f(q) = f(pq)\) ，则认为函数 \(f\) 为完全积性函数

常见的积性函数有：

元函数 \(\epsilon\) ：\(\epsilon (n) = [n = 1]\) (完全积性)
恒等函数 \(I\) ：\(I(n) = 1\) (完全积性)
单位函数 \(id\) ：\(id(n) = n\) (完全积性)
莫比乌斯函数 \(\mu\)
欧拉函数 \(\varphi\) ：\(\varphi(n) = \sum_{i = 1} ^ n[\gcd(i, n) = 1]\)
约数个数 \(d\) ：\(d(n) = \sum_{i = 1} ^ n[i\ |\ n]\)
约数和 \(\sigma\) ：\(\sigma(n) = \sum_{i = 1}^ni\cdot[i\ |\ n]\)

常见性质有：

对于任意函数 \(f\) ，\(f * \epsilon = f\)
\(\mu * I = \epsilon\)
\(\varphi * I = id\)
\(\begin{align*} \frac {\varphi(n)}n = \sum_{d|n} \frac{\mu(d)}d \end{align*}\)

杜教筛

已知 \(f\) 为积性函数，求 \(S(n) = \sum_{i = 1} ^ n f(i)\) ，\(n \le 10^{10}\)

显然直接做是肯定不行的，考虑构造一个函数 \(g\) ，使得 \(g\) 以及 \(f * g\) 的前缀和很好求（可以 \(O(1)\) 求）

找到这样的函数 \(g\) （一般是上面常见的几个积性函数或它们的次方），就可以开始推式子了qwq

\[\begin{align*} \sum_{i = 1} ^ n (f * g)(i) = \sum_{i = 1} ^ n \sum_{d | i} f(d) g(\frac id) \end{align*} \]

显然 \(\frac id\) 的范围为 \([1,n]\) 所以可以枚举 \(\frac id\) ，用 \(i\) 代替 \(\frac id\) ，可得

\[\begin{align*} \sum_{i = 1} ^ n (f * g)(i) &= \sum_{i = 1} ^ n \sum_{d | i} f(d) g(\frac id) \\ &= \sum_{i = 1} ^ ng(i)\sum_{j = 1} ^ {\lfloor \frac ni\rfloor} f(j) \\ &= \sum_{i = 1} ^ ng(i)S(\lfloor \frac ni\rfloor) \end{align*} \]

由于我们要求 \(S(n)\) ，那么显然在上面的式子中当 \(i = 1\) 时有一个 \(S(n)\) ，把它分离出来

\[\begin{align*} \sum_{i = 1} ^ n (f * g)(i) &= \sum_{i = 1} ^ ng(i)S(\lfloor \frac ni\rfloor) \\ &= g(1) S(n) + \sum_{i = 2} ^ n g(i)S(\lfloor \frac ni\rfloor) \end{align*} \]

于是得出关键式子：

\[g(1)S(n) = \sum_{i = 1} ^ n (f * g)(i) - \sum_{i = 2} ^ n g(i)S(\lfloor \frac ni\rfloor) \]

可以预处理出 \(M\) 以内的 \(g ,f, f * g\) 的前缀和（\(M\) 为线性可接受的值，一般为 \(\sqrt n\)），递归求解 \(S(n)\) ，时间复杂度 \(O(n^{\frac 23})\) ，证明不会

大致代码结构

inline int sum_g(const int &x) // 求 g(1) + ... + g(x)
{
    ...
}
inline int sum_fg(const int &x) // 求 (f * g)(1) + .. + (f * g)(x)
{
    ...
}
inline int sum_f(const int &x) // 求 S(x)
{
    if (x <= M) return S[x]; // 预处理的值
    if (mp[x]) return mp[x]; // map 记忆化
    int ans = sum_fg(x); // 求 f * g 的前缀和
    for (int l = 2, r; l <= x; l = r + 1) // 注意不要从 1 开始
    {
        r = x / (x / l); // 整出分块
        int res = sum_g(r) - sum_g(l - 1); // g(l) + .. + g(r)
        ans = (ans - res * sum_f(x / l));
    }
    return mp[x] = ans;
}

当然杜教筛难就难在求合适的 \(g\) ，对于 \(g\) 难求的问题，可以用 min_25 筛或 powerful number 筛，但是我完全不会 /kk ，这个只能请教数论代师HS了。

例题

莫比乌斯函数之和

题意：

已知 \(a, b\) ，求：

\[\sum_{i = a} ^ b \mu(i) \]

先求前缀和再差分，再根据常用性质 ，\(\mu * I = \epsilon\) ，所以 \(g = I, f * g = \epsilon\) ，直接做

最小公倍数之和 V3

题意：

已知 \(n\) ，求：

\[\sum_{i = 1} ^n \sum_{j = 1} ^n \text{lcm}(i, j) \]

推式子：

\[\begin{align*} &\sum_{i = 1} ^n \sum_{j = 1} ^n \text{lcm}(i, j) \\ =& \sum_{i = 1} ^n \sum_{j = 1} ^n \frac{ij}{\gcd(i, j)} \\ =&\sum_{d = 1} ^ n \sum_{i = 1} ^ {\lfloor \frac n d \rfloor} \sum_{j = 1} ^ {\lfloor \frac n d \rfloor} \frac{id \cdot jd} d [\gcd(i, j) = 1] \\ =&\sum_{d = 1} ^ n d \sum_{i = 1} ^ {\lfloor \frac n d \rfloor} \sum_{j = 1} ^ {\lfloor \frac n d \rfloor} ij [\gcd(i, j) = 1] \\ &\because\sum_{i = 1} ^ n i [\gcd(i, n) = 1] = \frac{\varphi(n)} 2 n \\ \therefore=&\sum_{d = 1} ^ nd\sum_{i= 1} ^ {\lfloor \frac n d \rfloor} i^2\varphi(i) \end{align*} \]

考虑快速求 \(S(\lfloor \frac n d \rfloor) = \begin{align*} \sum_{i= 1} ^ {\lfloor \frac n d \rfloor} i^2\varphi(i) \end{align*}\)

显然，如果 \(f(i) = i^2\varphi(i)\) ，则 \(g = id^2, f * g = \varphi(i)\) 是个不错的选择

两个整除分块就行了

约数之和

题意：

已知 \(n\) ，求：

\[\sum_{i = 1} ^ n \sum_{j = 1}^n \sigma(i \cdot j) \]

巨难推，我不会，HS切，Orz

码农公寓