$BZOJ$2818 $gcd$ 莫比乌斯反演/欧拉函数
2024-09-06 20:57:56
正解:莫比乌斯反演/欧拉函数
解题报告:
一步非常显然的变形,原式=$\sum_{d=1,d\in prim}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==d]$
后面那个就莫比乌斯反演入门题辣$QwQ$?
就变成$\sum_{p=1}^{n}[p\mbox{为质数}]\sum_{d=1}^{n/p}\mu(d)\lfloor \frac {n/p}{d}\rfloor^2$
十分套路的,后面显然可以数论分块,就变成了$\sum_{p=1}^{n}[p\mbox{为质数}] cal(\lfloor\frac{n}{p}\rfloor)$
于是前面就也能数论分块?考虑再前缀和一个质数个数.然后把前面也数论分块.
也就做两次数论分块,然后复杂度是$O(n)$的$QwQ$
$over$!
然后另一个方法其实$easy$蛮多$QwQ$
你考虑到化出的第一个式子去,显然能想到变形成$\sum_{d=1,d\in prim}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,j)==1]$
看到后面这个,联想到欧拉函数,发现$\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,j)==1]$的答案其实也就$\lfloor\frac{n}{d}\rfloor$内的欧拉函数前缀和乘二减一?(乘二是因为交换顺序嘛,减一是因为算重了$(1,1)$这一对嘛$QwQ$
就$easy$些$QwQ$
代码可以去看加强版
最新文章
- llinux 查看自己的公网ip
- linux 下 jdk tar.gz 包安装方法
- JDBC的批量批量插入
- 解决SQL数据库无法脱机的问题
- HTML XML XHTML DHTML区别与联系
- 解决Android SDK Manager更新(一个更新Host的程序的原理实现和源码)
- Linux 高可用(HA)集群基本概念详解
- web 前端routine
- Vscode 插件
- [Swift]LeetCode39. 组合总和 | Combination Sum
- js及jsp区别
- 两个队列实现栈&;两个栈实现队列(JAVA)
- zabbix添加对haproxy的监控
- 图解安装Debian 9.5全过程
- BZOJ.3551.[ONTAK2010]Peaks加强版(Kruskal重构树 主席树)
- php包含那点事情[WOOYUN]
- 5种实现垂直居中css
- 知识点查缺补漏贴01-进程间通讯之mmap文件共享
- 在操作Centos系统时经常出现You have new mail in /var/spool/mail/root提示怎么回事?
- 延期年金(deferred annuity)
热门文章
- MapReduce数据流-Mapper
- OpenResty,X-WAF防火墙相关
- linux lvm删除导致无法启动
- 2018-11-19-win10-uwp-使用-Matrix3DProjection-进行-3d-投影
- Unity 鼠标控制视角功能和动画播放冲突解决办法
- Java Integer类的缓存
- tensorflow学习笔记(四十五):sess.run(tf.global_variables_initializer()) 做了什么?
- java什么叫面向对象?
- [转]vue - 前置工作 - 目录功能介绍
- tsung测试xmpp遇到no_free_userid