杜教筛

杜教筛用来解决积性函数前缀和的问题，可以在低于线性的时间复杂度内求出前缀和

求欧拉函数前缀和

记欧拉函数前缀和
已知
所以
先枚举则原式等于
上面一步相当于先枚举其中一个因子为,则只要那么就一定是中某个数的因子，而原式的含义就是将中所有数的因子的相加
然后我们发现
所以
右边部分可以预处理大约个，再用整除分块解决

求莫比乌斯函数前缀和

和求欧拉函数前缀和一样，记前缀和
所以
则
显然只有取的时候后面值为，其余都是
参照上面，最后可以化简为
同样预处理个，然后整除分块处理

对于一般的积性函数

记

则