杜教筛

---

作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)

---

积性函数

若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。

常见积性函数：

1. \(\mu()\) ——莫比乌斯函数。
2. \(\phi()\) ——欧拉函数。\(\phi(n)=\sum_{i=1}^n [gcd(n,i)=1]\)
3. \(d()\) ——约数个数。\(d(n)=\sum_{i=1}^n[i|n]\)
4. \(\sigma()\) ——约数和函数。\(\sigma(n)=\sum_{i=1}^n[i|n]*i\)

积性函数中的特殊存在完全积性函数，即不需满足 \(gcd(a,b)=1\) 的积性函数。

常见的完全积性函数：

1. $ \epsilon()$ ——元函数。$ ϵ(n)=[n=1]$
2. \(I()\) ——恒等函数。\(I(n)=1\)
3. \(id()\) ——单位函数。\(id(n)=n\)

---

狄利克雷卷积，假设符号为 \(*\)

定义：两个数论函数的狄利克雷卷积为 \((f*g)(n)=\sum_{d|n} f(d)*g(\frac{n}{d})\)

很显然，狄利克雷卷积满足以下运算规律：

1. 交换律 \((f∗g=g∗f)\)
2. 结合律 \(((f∗g)∗h=f∗(g∗h))\)
3. 分配律 \(((f+g)∗h=f∗h+g∗h)\)

举例：对于数论函数 \(f\) ，\(f=f*\epsilon\)

---

杜教筛

假设我们要计算 \(\sum_{i=1}^n f(i)\) (\(f(i)\)为积性函数)

第一步： 构造两个积性函数 \(h\) 和 \(g\) ，使得 \(h=f*g\)

第二部：推式子，设 \(S(n)=\sum_{i=1}^n f(i)\)

\[\sum_{i=1}^n h(i)=\sum_{i=1}^n \sum_{d|i}g(d)*f(\frac{n}{d}) \]

\[\sum_{i=1}^n h(i)=\sum_{d=1}^n g(d)*\sum_{i=1}^\left\lfloor\frac{n}{d}\right\rfloor f(i) \]

\[\sum_{i=1}^n h(i)=\sum_{d=1}^n g(d)*S(\left\lfloor\frac{n}{d}\right\rfloor) \]

接着，我们将右边式子的第一项给提出来，可以得到：

\[\sum_{i=1}^n h(i)=g(1)*S(n)+\sum_{d=2}^n g(d)*S(\left\lfloor\frac{n}{d}\right\rfloor) \]

\[g(1)*S(n)=\sum_{i=1}^n h(i)-\sum_{d=2}^n g(d)*S(\left\lfloor\frac{n}{d}\right\rfloor) \]

这样的话，\(S(n)\) 就可以递归求解。

对于积性函数 \(h\) 和 \(g\) 选择要靠自己总结。

---

小试身手

假如我们要求的 \(f\) 函数为 \(\mu\) ，显然 \(\epsilon=\mu*I\) ，即 \(h\) 函数为 \(\epsilon\) ，\(g\) 函数为 \(I\)

代入到上面杜教筛的式子中，\(I(1)*S(n)=\sum_{i=1}^n\epsilon(i)-\sum_{d=2}^n I(d)*S(\left\lfloor\frac{n}{d}\right\rfloor)\)

即 \(S(n)=1-\sum_{d=2}^n S(\left\lfloor\frac{n}{d}\right\rfloor)\) ，\(\left\lfloor\frac{n}{d}\right\rfloor\) 明显可以整除分块。

整除分块、记忆化搜索即可。

假如我们要求的 \(f\) 函数为 \(\phi\) ，显然 \(id=\phi*I\) ，即 \(h\) 函数为 \(id\) ，\(g\) 函数为 \(I\)

代入到上面杜教筛的式子中，\(I(1)*S(n)=\sum_{i=1}^nid(i)-\sum_{d=2}^n I(d)*S(\left\lfloor\frac{n}{d}\right\rfloor)\)

即 \(S(n)=\frac{(n+1)*n}{2}-\sum_{d=2}^n S(\left\lfloor\frac{n}{d}\right\rfloor)\) ，\(\left\lfloor\frac{n}{d}\right\rfloor\) 明显可以整除分块。

整除分块、记忆化搜索即可。

假如我们要求的 \(f\) 函数为 \(d\) (约数个数函数) ，用莫反推得 \(I=d*\mu\) ，即 \(h\) 函数为 \(I\) ，\(g\) 函数为 \(\mu\)

代入到上面杜教筛的式子中，\(\mu(1)*S(n)=\sum_{i=1}^nI(i)-\sum_{d=2}^n \mu(d)*S(\left\lfloor\frac{n}{d}\right\rfloor)\)

即 \(S(n)=n-\sum_{d=2}^n \mu(d)*S(\left\lfloor\frac{n}{d}\right\rfloor)\) ，\(\mu\) 前缀和可以再用一次杜教筛。

整除分块、记忆化搜索即可。

---

总结：杜教筛思维上并不是很难，但需要基础数论知识较多。