杜教筛

1. 积性函数

1. 算术函数/数论函数：定义在所有正整数上的函数
2. 积性函数/乘性函数：算术函数 f 满足对于所有 \(p,q\in N,(p,q)=1\)，有 \(f(pq)=f(p)f(q)\)，那么 f 称为积性函数
3. 完全积性函数：算术函数 f 满足对于所有 \(p,q\in N\)，有 \(f(pq)=f(p)f(q)\)，那么 f 称为完全积性函数

若 f 是积性函数，那么 f 的和函数 \(F(n)=\sum\limits_{d|n}f(d)\) 也是积性函数

1. （一次或多次）计算第 i 项
2. 前缀和 \(\sum\limits_{i=1}^nf(i)\)

1. 恒等函数：\(I(n)=1\)
2. 单位函数：\(\text{id}(n)=n\)
3. 幂函数：\(I_k(n)=n^k\)
4. 元函数：\(\epsilon(n)=\begin{cases}1&n=1\\0&n>1\end{cases}=[n=1]\)
5. 因子和函数：\(\sigma(n)=\sum\limits_{d|n}d\)
6. 约数个数：\(\tau(n)=\sum\limits_{d|n}1\)