杜教筛

杜教筛

杜教筛的核心

用途：

用于低于线性时间里，高效率求一些积性函数的前缀和

算法：

说简单点就是整除分块+狄利克雷卷积+线性筛

公式：

积性函数

常见的积性函数

两个重要定理：

狄利克雷卷积

莫比乌斯反演：

杜教筛

公式：

推一个具体的式子：

//代码#include using namespace std;typedef long long ll;const int maxn = 5e6+7; //超过n^(2/3)，够大了int prime[maxn]; //记录质数bool vis[maxn]; //记录是否被筛；int mu[maxn]; //莫比乌斯函数值ll phi[maxn]; //欧拉函数值unordered_map summu; //莫比乌斯函数前缀和unordered_map sumphi; //欧拉函数前缀和void init(){ //线性筛预计算一部分答案 int cnt = 0; vis[0] = vis[1] = 1; mu[1] = phi[1] = 1; for(int i=2;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。