搜索结果
查询Tags标签： 杜教，共有 8条记录-
数论分块、杜教筛思想、莫比乌斯反演初探
1 1.对于L,R；2 找到最大的R，使得[n/l]=[n/r];3 n/r>=[n/r]-->r<=n/[n/r] 4 <<=>>5 r<=n/[n/l];6 7 2.8 [[n/x]/y]=[n/xy]9 10 3.杜教筛 11 i >= 1 && i <= n j >= 1 && j <= n 12 求它们的互质对数 13 令f(n)=它…
2022/4/10 23:13:09 人评论 次浏览 -
【模板】杜教筛（Sum）
\(\text{Code}\) #include<cstdio> #include<tr1/unordered_map> #define LL long long using namespace std; const int M = 5e6; int vis[M + 5],p[M + 5],tot,T,n; LL phi[M + 1],mu[M + 1];tr1::unordered_map<int,LL> fm,fp; void init() {mu[1] =…
2022/3/9 23:19:23 人评论 次浏览 -
浅谈杜教筛
今天本身是要学习莫比乌斯反演的，然后题单里面出现了一道需要用杜教筛的题，我还推到了只剩杜教筛的地方 于是迫不得已学习了这种神仙算法，真是迫不得已啊。。。。 杜教筛是一种在线性复杂度以下的求积性函数前缀和的高级算法，大概在\(O(n^{\frac{2}{3}})\)左右 前置知…
2021/11/1 6:39:29 人评论 次浏览 -
浅谈杜教筛
今天本身是要学习莫比乌斯反演的，然后题单里面出现了一道需要用杜教筛的题，我还推到了只剩杜教筛的地方 于是迫不得已学习了这种神仙算法，真是迫不得已啊。。。。 杜教筛是一种在线性复杂度以下的求积性函数前缀和的高级算法，大概在\(O(n^{\frac{2}{3}})\)左右 前置知…
2021/11/1 6:39:29 人评论 次浏览 -
杜教筛
杜教筛作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)积性函数 若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。 常见积性函数：\(\mu()\) ——莫比乌斯函数。 \(\phi()\) ——欧拉函数。\…
2021/10/6 23:13:28 人评论 次浏览 -
杜教筛
杜教筛作用：用来求积性函数前缀和，时间复杂度为\(O(n^\frac{2}{3})\)积性函数 若对于函数 \(f(x)\) 满足 \(f(x)=f(a)*f(b)\) ，其中 \(x=a*b\) 且 \(gcd(a,b)=1\)，那么 \(f(x)\) 为积性函数。 常见积性函数：\(\mu()\) ——莫比乌斯函数。 \(\phi()\) ——欧拉函数。\…
2021/10/6 23:13:28 人评论 次浏览 -
[算法入门]杜教筛
#1.0 基础知识 #1.1 积性函数 #1.1.1 定义 设 \(f\) 是数论函数，若对任意互质的正整数 \(a,b\)，都有 \(f(ab)=f(a)f(b)\)，则称 \(f\) 是积性函数。若对任意的正整数 \(a,b\)，都有 \(f(ab)=f(a)f(b)\)，则称 \(f\) 是完全积性的。 #1.1.2 性质 若 \(f\) 是积性函数，且…
2021/6/11 20:21:37 人评论 次浏览 -
51nod 1244 莫比乌斯函数之和(杜教筛)
基准时间限制：3 秒 空间限制：131072 KB 分值: 320 难度：7级算法题收藏关注莫比乌斯函数，由德国数学家和天文学家莫比乌斯提出。梅滕斯(Mertens)首先使用μ(n)（miu(n)）作为莫比乌斯函数的记号。具体定义如下： 如果一个数包含平方因子，那么miu(n) = 0。例如：miu(4)…
2021/6/5 10:22:40 人评论 次浏览
