Loj6181 某个套路求和题 【min25筛+莫比乌斯反演】
发布日期：2021-05-06 15:54:45
浏览次数：21
分类：技术文章
本文共 785 字，大约阅读时间需要 2 分钟。
f ( n ) f(n) f(n) 在质数处为 − 1 -1 −1 ，有平方因子时为 0 0 0 ，其余为 1 1 1 。
考虑算出无平方因子的个数，再减去质数的个数。
算质数的个数就是 M i n 25 Min25 Min25 筛计算。
前者就是算 ∑ μ 2 \sum \mu^2 ∑μ2 ，记 p ( x ) = max d 2 ∣ x { d } p(x)=\max_{d^2|x}\{d\} p(x)=maxd2∣x{ d}
∑ i = 1 n μ 2 ( i ) = ∑ i = 1 n [ p ( i ) = 1 ] = ∑ d = 1 n μ ( d ) ⌊ n / d 2 ⌋ P S : H x 表示 p 是 x 的倍数的数的个数， h x 表示 p 是 x 的数的个数，莫比乌斯反演一下即可 \begin{aligned} &\sum_{i=1}^n \mu^2(i) \\ =&\sum_{i=1}^{n}[p(i)=1] \\ =&\sum_{d=1}^{n}\mu(d)\lfloor n/d^2\rfloor\\ & PS: H_x\text{ 表示 }p \text{ 是 }x\text{ 的倍数的数的个数， }\\ &h_x \text{ 表示 }p \text{ 是 }x\text{ 的数的个数，莫比乌斯反演一下即可 } \end{aligned} ==i=1∑nμ2(i)i=1∑n[p(i)=1]d=1∑nμ(d)⌊n/d2⌋PS:Hx 表示 p 是 x 的倍数的数的个数， hx 表示 p 是 x 的数的个数，莫比乌斯反演一下即可 第一步到第二步就是莫比乌斯反演一下就可以了。已经时个整除分块的形式了， n \sqrt n n 计算答案。最终复杂度 O ( n 3 / 4 ) O(n^{3/4}) O(n3/4) 。
发表评论
最新留言
很好
[***.229.124.182]2025年03月29日 01时56分24秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
PYTHON UDP只能接收本地报文，无法接收其他主机通过路由器发过来的报文
2019-03-03
QLabel控件功能示例
2019-03-03
vue项目中报/sockjs-node/info错误
2019-03-03
如何处理前任程序员留下的代码
2019-03-03
20个非常有用的Java程序片段
2019-03-03
如何锻炼JAVA编程思路？
2019-03-03
Mybatis源码分析(四)：属性接口之objectFactory
2019-03-03
全面了解 Nginx 主要应用场景
2019-03-03
最全的spring面试题和答案
2019-03-03
CentOS 8 已下载ntpdate 却无法使用crond进行时间同步
2019-03-03
Mybatis的这些坑！把我坑惨了！
2019-03-03
在 IntelliJ IDEA 中使用 Git，太方便了！
2019-03-03
7 个显著提升编码效率的IntelliJ IDEA必备插件
2019-03-03
企业API接口设计之token、timestamp、sign具体实现
2019-03-03
不懂别瞎搞！Redis 性能优化的 13 条军规！
2019-03-03
卸载 Navicat！事实已证明，正版客户端，它更牛逼……
2019-03-03
想彻底了解maven，有这篇文章足够了(中)
2019-03-03
Intellij IDEA 一些让人爱不释手的小技巧
2019-03-03
idea连接服务器远程调试（Dockerfile版）
2019-03-03
ElasicJob分布式定时任务
2019-03-03
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 453512118 位访客