杜教筛
杜教筛公式
\[\begin{aligned}
h &= f \ast g
\\
h(i) &= f \ast g (i)
\\
&= \sum\limits_{d|i} f(d) g(\frac{i}{d})
\\
\sum\limits_{i=1}^{n} h(i) &= \sum\limits_{i=1}^{n} \sum\limits_{d|i} f(d) g(\frac{i}{d})
\\
&= \sum\limits_{i=1}^{n} \sum\limits_{d|i} g(d) f(\frac{i}{d})
\\
&= \sum\limits_{d=1}^{n} g(d) \sum\limits_{d|i}^{n} f(\frac{i}{d})
\\
&= \sum\limits_{d=1}^{n} g(d) \sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor} f(i)
\\
&= \sum\limits _{d=1}^{n} g(d) S(\lfloor \frac{n}{d} \rfloor)
\\
&= \sum\limits_{i=1}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)
\\
&= g(1) S(n) + \sum\limits_{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)
\\
g(1) S(n) &= \sum\limits_{i=1}^{n} h(i) - \sum\limits_{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)
\end{aligned}
\]
欧拉函数前缀和
由于 \(n = \sum\limits_{d|n} \varphi(d)\)，构造 \(f = \varphi, g = 1\)，则 \(h = \varphi \ast 1\)，则有：
\[\begin{aligned}
h(i) &= \sum\limits_{d|i} \varphi(d) 1(\frac{i}{d})
\\
&= \sum\limits_{d|i} \varphi(d)
\\
&= i
\\
&= id(i)
\end{aligned}
\]
代入杜教筛公式，得：
\[\begin{aligned}
1(1) S(n) &= \sum\limits_{i=1}^{n} id(i) - \sum\limits_{i=2}^{n} 1(i) S(\lfloor \frac{n}{i} \rfloor)
\\
S(n) &= \sum\limits_{i=1}^{n} i - \sum\limits_{i=2}^{n} S(\lfloor \frac{n}{i} \rfloor)
\\
&= \frac{n(n+1)}{2} - \sum\limits_{i=2}^{n} S(\lfloor \frac{n}{i} \rfloor)
\end{aligned}
\]
观察到式中出现 \(\lfloor \frac{n}{i} \rfloor\) 的形式，可以考虑利用整除分块求解。
莫比乌斯函数前缀和
定理：\(\sum\limits_{d|n} \mu(d) = \varepsilon(n)\)
证明：
对于 \(n=1\)，显然有 \(\sum\limits_{d|n} \mu(d) = 1\)
对于其他情况：
设 \(n = \prod\limits_{i=1}^{k} p_i^{c_i},n' = \prod\limits_{i=1}^{k}p_i\)。
由于对于一个 \(n\) 的因数 \(d\)，若它的某一个质因数 \(p_i\) 的指数 \(c_i > 1\)，则 \(\mu(d) = 0\)，对 \(\sum\limits_{d|n} \mu(d)\) 无贡献，可得：
\[\sum\limits_{d|n} \mu(d) = \sum\limits_{d|n'} \mu(d) = \sum\limits_{i=0}^{k} \tbinom{k}{i} (-1)^{i} = \sum\limits_{i=0}^{k} \tbinom{k}{i} (-1)^i 1^{k-i}
\]
根据二项式定理展开，得：
\[\sum\limits_{d|n} \mu(d) = (-1+1)^k = 0^k = 0
\]
所以：
\[\sum\limits_{d|n} \mu(d) =
\left\{
\begin{matrix}
1 \thinspace (n=1)
\\
0 \thinspace (n>1)
\end{matrix}
\right.
= \varepsilon(n)
\]
构造 \(\varepsilon = \mu \ast 1\)，则有：
\[\begin{aligned}
1(1) S(n) &= \sum\limits_{i=1}^{n} \varepsilon(i) - \sum\limits_{i=2}^{n} 1(i) S(\lfloor \frac{n}{i} \rfloor)
\\
S(n) &= \sum\limits_{i=1}^{n} \varepsilon(i) - \sum\limits_{i=2}^{n} S(\lfloor \frac{n}{i} \rfloor)
\\
&= 1 - \sum\limits_{i=2}^{n} S(\lfloor \frac{n}{i} \rfloor)
\end{aligned}
\]