fkmu
2024-09-16 06:06:59
杭州赛区J：考虑实质上是求解 (a,b) = 1 且 a*b<=n的数对个数，枚举a，对b容斥。
trickgcd：考虑反向求解，即为ans[x] -= ans[t*x]，注意到因为反向求所以余下的刚好为实际值。
Winter is here：同上容斥傻题，C(n,1) + 2C(n,2) +... + n*C(n,n) 可以用多项式 (x+1)^n 求导 x = 1得到。
gcdpower：枚举r，维护l从1~r-1的答案，可以注意到每次对于加入的ar，只可以作为原式中的ak，找到前面的ar的倍数，
用树状数组进行区间更新即可，对于i找到(ai,aj) = ak相当于 (ai/ak,aj/ak) = 1，用一个数组记下后缀aj/ak，对ai质因子进行容斥即可。
复杂度分析同上题。
最新文章
- magic方法的magic
- 深入学习jQuery选择器系列第五篇——过滤选择器之内容选择器
- asp.net ajax控件tab扩展，极品啊，秒杀其它插件
- 二、JavaScript语言--JS实践--信息滚动效果制作
- 标准W3C盒子模型和IE盒子模型
- Java 实现阶乘算法
- EL表达式中如何截取字符串
- SpringMVC ResponseBody返回中文乱码解决方案
- WF学习笔记（三）
- Java笔记原生数据类型【二】
- Hibernate学习笔记（一）：mycelipse建立项目流程（未完成）
- 并发数据（锁）ReaderWriterLockSlim
- 一日一练-CSS-CSS 居中
- C语言面试笔记（8/26）
- Linux系统下我的/etc/sysconfig/路径下无iptables文件
- CentOS下Docker安装
- 廖雪峰Java2面向对象编程-1面向对象-1面向对象基础
- 关于cookie的一些事
- 给iOS开发新手送点福利,简述UISwitch的属性和用法
- Go Methods and Interfaces