欧拉筛【转载自用
2021/5/22 10:25:14
本文主要是介绍欧拉筛【转载自用,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言 https://www.luogu.com.cn/blog/HSH/post-shuo-lun-ou-la-shai-fa
最近学数论,我是真的绝望,欧拉筛法也只能靠背代码勉强凑合凑合,但在我社CSQ大佬的帮助下,我理解到了其中神奇的奥妙
正题
欧拉筛法是一种可以筛出质数,欧拉函数,约数个数和约数和的筛法 那么我们就对这些问题逐一进行讲解
在这之前,我们先说几个东西:
1、每一个大于等于2的正整数nn,都有n=p_1^{w_1}p_2^{w_2}…p_m^{w_m}n=p1w1p2w2…pmwm(p_1p1到p_mpm按升序排列)
2、正整数nn的欧拉函数phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_m})=p_1^{w_1-1}(p_1-1)*p_2^{w_2-1}(p_2-1)*…*p_m^{w_m-1}(p_m-1)phi(n)=n(1−p11)(1−p21)…(1−pm1)=p1w1−1(p1−1)∗p2w2−1(p2−1)∗…∗pmwm−1(pm−1)
3、正整数nn的约数个数d(n)=(1+w_1)(1+w_2)…(1+w_m)d(n)=(1+w1)(1+w2)…(1+wm)
4、正整数nn的约数和s(n)=(1+p_1+p_1^2+…+p_1^{w_1})(1+p_2+p_2^2+…+p_2^{w_2})……(1+p_m+p_m^2+…+p_m^{w_m})s(n)=(1+p1+p12+…+p1w1)(1+p2+p22+…+p2w2)……(1+pm+pm2+…+pmwm)
质数
代码
inline void sieve(int x) { for(reg int i = 2;i <= x;i ++) { if(! vis[i]) prim[++ len] = i; for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) break; } } }
欧拉函数
代码
inline void sieve(int x) { phi[1] = 1; for(reg int i = 2;i <= x;i ++) { if(! vis[i]) { prim[++ len] = i; phi[i] = i - 1; //因为欧拉函数代表小于这个数的且与这个数互质的数的个数,所以质数的欧拉函数为它本身减1 } for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) { phi[i * prim[j]] = phi[i] * prim[j]; break; } phi[i * prim[j]] = phi[i] * (prim[j] - 1); } } }
约数个数
代码
inline void sieve(int x) { for(reg int i = 2;i <= x;i ++) { if(! vis[i]) { prim[++ len] = i; d[i] = 2; //质数的约数只有1和它本身 sum[i] = 1; } for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) { sum[i * prim[j]] = sum[i] + 1; d[i * prim[j]] = d[i] / (sum[i] + 1) * (sum[i] + 2); break; } sum[i * prim[j]] = 1; d[i * prim[j]] = d[i] * 2; } } }
约数和
代码
inline void sieve(int x) { for(reg int i = 2;i <= x;i ++) { if(! vis[i]) { prim[++ len] = i; psum[i] = s[i] = i + 1; } for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) { psum[i * prim[j]] = psum[i] * prim[j] + 1; s[i * prim[j]] = s[i] / psum[i] * psum[i * prim[j]] break; } psum[i * prim[j]] = prim[j] + 1; s[i * prim[j]] = s[i] * psum[i * prim[j]]; } } }
这篇关于欧拉筛【转载自用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)