搜索结果
查询Tags标签： 积性，共有 5条记录-
看起来很高级的符号
rt，其实是用来方便自己学莫比乌斯反演的......像 \(\sum\) 这种东西干嘛要加，反正是给我自己看看的...... \(\varphi(n)\)：\(\sum\limits_{i=1}^{n-1}\left[gcd(n, i) = 1\right]\) \(\tau(n)\)：\(n\) 的约数个数。 \(\sigma(n)\)：\(n\) 的约数之和。 \(d_k(n)\)：约…
2022/8/27 23:22:47 人评论 次浏览 -
莫比乌斯反演自我击毙进程1-1
前情提要：关于莫比乌斯翻译，是真的懵逼吾死，莫比乌斯函数（好理解），狄利克雷卷积（能懂不会用），莫比乌斯反演（队友泪两行），杜教筛（呵呵），因为看了两天自己不能自理的推出来，所以写个博客帮助下理解，懂了就改。。。。。。。 需要提前知道的知识： 积性函数：…
2022/7/6 5:20:36 人评论 次浏览 -
数论分块、杜教筛思想、莫比乌斯反演初探
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 人评论 次浏览 -
筛法、积性函数、欧拉定理、裴蜀定理、扩欧 总结
啊啊啊快吐了。。。。。。。。。。 筛质数 埃筛 对于每一个质数，标记它的所有倍数(除了它本身)为合数。 时间复杂度：\(\mathcal {O}(nlog(log(n)))\)。 拓展1：\(1\sim n\) 中质数约有 \(n/ln(n)\) 个。 拓展2：\(1\sim n\) 中质因数约有 \(nlog(log(n))\) 个。（由埃筛…
2021/8/19 23:35:51 人评论 次浏览 -
筛法、积性函数、欧拉定理、裴蜀定理、扩欧 总结
啊啊啊快吐了。。。。。。。。。。 筛质数 埃筛 对于每一个质数，标记它的所有倍数(除了它本身)为合数。 时间复杂度：\(\mathcal {O}(nlog(log(n)))\)。 拓展1：\(1\sim n\) 中质数约有 \(n/ln(n)\) 个。 拓展2：\(1\sim n\) 中质因数约有 \(nlog(log(n))\) 个。（由埃筛…
2021/8/19 23:35:51 人评论 次浏览
