loj6165 一道水题（线性筛）
2024-08-30 14:45:29
题目：
分析：
最直接的想法就是把1~n的所有数分解质因数，然后每个素数的幂取max
我们首先来看看一共可能有哪些素数？
实际上这些素因数恰好就是1~n内的所有的素数，那ok，线性筛O(n)解决
接下来就是每个p的指数了
对于每个p，最大的其实就是p^k<=n的最大的k，这里直接从小到大枚举k就行了
因为素数的个数有n/ln(n)个，每个素数最多枚举log次，所以总的时间复杂度O(n)
最新文章
- 看看C# 6.0中那些语法糖都干了些什么（终结篇）
- [转]单点登录SSO学习——CAS协议内容
- BZOJ 1088 扫雷Mine
- []with[[]]
- 无法从命令行或调试器启动服务，必须首先安装Windows服务(使用installutil.exe),然后用ServerExplorer、Windows服务器管理工具或NET START命令启动它
- PHP中用下划线开头的变量含义
- struts2 I18N 国际化
- uart与usart
- MyBatis笔记——初次环境配置
- cocos2dx 环境搭建 win7 +vs2012+ cocos2dx-2.1.4
- ORACLE RMAN介绍
- 分布式版本控制系统Git-----9.Git 使用的小技巧
- activiti 5.15.1 动态手动通过java编码方式，实现创建用户任务，动态指定个人，用户组，角色，指定监听的实现
- Java Annotation注解继承说明
- BZOJ-1010-[HNOI2008]玩具装箱toy（斜率优化）
- 云技术：负载均衡SLB
- 双系统下Ubuntu扩展根目录空间方法
- 转:Linux下查看tomcat占用端口
- 10个JavaScript难点
- [LeetCode&Python] Problem 520. Detect Capital