求1到n的质数个数和O(n)
2024-10-02 06:31:47
也许更好的阅读体验
\(\mathcal{AIM}\)
我们知道:
对于一个合数\(x\) 有\(x=p^{a_1}_1*p^{a_2}_2*...*p^{a_n}_n\)
现在给出一个\(n\) 求\(x\in[1,n]\),所有\(x\)分解出的\(p\)的幂数和
例如
\(n=12\)
\(2=2^1\)
\(3=3^1\)
\(4=2^2\)
\(5=5^1\)
\(6=2^1*3^1\)
\(7=7^1\)
\(8=2^3\)
\(9=3^2\)
\(10=2^1*5^1\)
\(11=11^1\)
\(12=2^2*3^1\)
数字 | 个数 |
---|---|
2 | 10 |
3 | 5 |
5 | 2 |
7 | 1 |
11 | 1 |
\(\mathcal{Resolvent}\)
对于一个合数\(x\) 有\(x=p^{a_1}_1*p^{a_2}_2*...*p^{a_n}_n\)
\(O(n\sqrt n)\)
这是最简单的想法,先记录哪些数是质数,再把\(n\)以内所有的数分解掉
int cnt;
int prime[maxn],num[maxn];//prime -> 求出来的质数 num -> 每个数出现个数
bool vis[maxn];//欧拉筛里看其是否是质数
ols(n);//这是欧拉筛
for (int i=1;i<=n;++i)
for (int j=1;j*j<=i&&j<=cnt;++j){
int t=i;
while (t%prime[j]==0) ++num[prime[j]],t/=prime[j];
}
\(O(nlog_2n)\)
考虑可不可以直接对整体求
这个方法对一些其他题也很有用
int cnt;
int prime[maxn],num[maxn];
bool vis[maxn];
ols(n);
for (int i=1;i<=cnt;++i){
int t=prime[i],mi=1;//mi -> mi次幂
while (t<=n){
num[prime[i]]+=n/t*mi;
t*=prime[i],++mi;
}
}
\(O(n)\)
对一个数 \(x\)
\(x/p_1\)显然是比\(x\)小的,若我们知道\(x/p_1\)的答案,那么\(x\)的贡献就是\(x/p_1\)的贡献加上对\(p_1\)的一个贡献
但我们把\(x/p_1\)的答案存下来只会增加复杂度
于是我们可以反过来循环,\(x\)先对\(p_1\)加一个贡献,之后我们就可以认为多了一个\(x/p_1\)了
计算\(x/p_1\)时答案就会多一,显然我们可以一直传递下去,这样每个数只用把自己最小质因子的贡献算出即可
int cnt;
int prime[maxn],num[maxn],come[maxn];//come[i] -> i的最小质因子
bool vis[maxn];
ols(n);
for (int i=n;i>=2;--i){
if (vis[i]){//如果是个合数
num[come[i]]+=num[i];//最小质因子加上当前这个数要计算次数
num[i/come[i]]+=num[i];//加上这个数需计算次数
num[i]=0;//当前这个数没了
}
}
最新文章
- Chrome/Firefox 中头toFixed方法四舍五入兼容性问题
- C#字符串操作 取文本左边 取文本右边 取文本中间 取文本中间到List集合 指定文本倒序
- eclipse如何快速查找某个类
- @SuppressWarnings(";deprecation";)
- mysql存储图片问题
- android 小记
- MySql的日常管理
- MVC小系列(十三)【全局异常处理与异常日志】
- HDU1232 畅通工程 (并查集模板题)
- LeetCode 319. Bulb Switcher
- UNIX环境高级编程——线程同步之读写锁以及属性
- Linux(Centos7)下搭建SVN服务器 (转载)
- cobble服务器安装配置
- CAS单点登录原理简单介绍
- NFS共享存储的使用
- web开发中xml的内容
- centos7如何查询已运行服务?
- linux分区命名
- 情人节网站logo赏析
- Java 存储和读取 oracle CLOB 类型字段的实用方法
热门文章
- 浅谈网络I/O多路复用模型 select &; poll &; epoll
- 给变量赋值,程序会跳到 HardFault_Handler的问题
- 取得文件夹内容信息(使用IShellFolder接口)
- C语言实现常用数据结构——图
- 很多程序员都没搞明白的时间与时区知识 - 24时区/GMT/UTC/DST/CST/ISO8601
- C语言指针学习总结
- composer使用本地仓库
- 从无到有构建vue实战项目(一)
- Jenkins+svn+ftp自动化发布asp.net项目
- springboot使用RabbitMQ实现延时任务