杜教筛
杜教筛是用来求一类积性函数和的算法。它的优点就在于它有着低于线性的时间复杂度。
直接应用杜教筛的时间复杂度是$O(n^{\frac{3}{4}})$。如果事先用线性筛处理$O(n^{\frac{2}{3}})$级别大小的前缀和，在杜教筛的递归过程中使用的话，时间复杂度会降到$O(n^{\frac{2}{3}})$。
因为杜教筛一般的数据规模都在$10^9$以上，所以要用某种数据结构保存那些$i$过大的$S(i)$。一般用map，如果时间效率要求高可以用一个数组：对于$i> \sqrt n$，保存$S(i)$到$\lfloor \frac{n}{i} \rfloor$位置。
欧拉函数
$\varphi$1
2