点击知行合一Gesp>点击右上角“···”>设为星标🌟
大家好，我是黄老师。 曾任职多家国有大型科技公司，具有多年C/C++实战经验，打造过数百万用户规模的电子终端产品。目前是一名少儿C++编程业余讲师，毕竟CSP也自称非专业。😁
已经完成《GESP一级保命系列》专栏，《GESP二级编程保命-字符图形》专栏以及《GESP二级编程保命-暴力枚举》专栏、GESP三级编程-一维数组、GESP三级编程-字符串、GESP三级编程-进制转换、GESP三级编程-位运算、GESP三级编程-排序等等三级专题，供大家参考。
现在推出《GESP五级数论》专栏，并会分享相关实践经验，与同学们一起学习、进步。🚀
往期精选
GESP五级的核心就是“数据结构（链表）+ 基础算法（二分、贪心、分治、递归）+ 数论应用”。备考时，精力可以按 7:3 分配在“算法与数论”和“链表”上。考纲只要求链表，熟练掌握链表的选择、判断题目，满分是首要目标；初等数论与筛法：欧几里得算法、素数筛法、唯一分解定理等，务必掌握代码模版，灵活运用；四大核心算法包括贪心算法、二分算法、分治算法、递归算法！
Prime（质数、素数）三法：试除、埃氏筛、欧拉筛
试除法是三级之前必备能力
适用于GESP一至四级
📌 为什么从 i² 开始标记？
埃氏筛法作为欧拉筛过渡
五级必备能力：能写能读
如果需要用筛法解题，就用欧拉筛，也称线性筛
五级
202509 数字选取
洛谷网P14073
↑微信扫码注册信奥公开课小程序↑
五级
题解思路
1. 题目分析
核心问题：
从 1 到 n 的整数中选取尽可能多的数
要求：选出的数两两互质（任意两个数的 gcd = 1）
求最大选取数量
关键观察：
1 与所有数互质，所以 1 总是可以选
质数之间互质，所以可以选所有质数
样例验证：
n=6：
可选方案：1, 5（质数），但还能选什么？
最优：{1, 2, 3, 5} → 4个 ✓
或者 {1, 4, 3, 5} → 4个
不能选5个数，因为1-6中，2,4,6共享因子2，最多选1个；3,6共享因子3，最多选1个；所以最多4个
n=9：
已知方案：{1, 5, 7, 8, 9} → 5个 ✓
验证互质：gcd(8,9)=1, gcd(8,5)=1, gcd(8,7)=1, gcd(9,5)=1, gcd(9,7)=1
为什么选8？因为8=2³，而2和4,6都不选，所以8与所有奇数质数互质
为什么选9？因为9=3²，而3和6都不选
如果8用2代替，9用3代替，那么选 {1} + {2, 3, 5, 7} → 5个 ✓
2. 建模思路
对于样例分析后，对于本题更优解题思路选择正确的贪心策略：先选择1，再选则2~n之间的所有质数
3. 算法选择
对于本题的 数据范围来说，刚好可以练习一下质数三法：试除法、埃氏筛和欧拉筛，都是可以AC的
五级
题解代码
试除法:
#include<bits/stdc++.h>using namespace std;/** 贪心策略：* 为了从 1,2,…,n 中挑尽量多个数，使它们互质，只选质数和 1。* 问题则变成了统计1,2,…,n 里有多少个质数，答案再加 1*/// 质数一：试除法boolisPrime(int x){for(int i=2; i<=sqrt(x); i++){if(x%i == 0) return false;}return x>=2;}intmain(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n; cin>>n;int cnt=1; // 首先选择数1，计数为1for(int i=2; i<=n; i++){if(isPrime(i)) cnt++;}cout << cnt << endl;return 0;}
埃氏筛法:
#include<bits/stdc++.h>using namespace std;/** 贪心策略：* 为了从 1,2,…,n 中挑尽量多个数，使它们互质，只选质数和 1。* 问题则变成了统计1,2,…,n 里有多少个质数，答案再加 1*/// 质数二：埃氏筛法，标记质数bool isPrime[100010];voidePrime(int n){// 初始化：全部设为 truefill(isPrime, isPrime + n + 2, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i <= sqrt(n); i++) {if (isPrime[i]) {// i 是质数，从 i*i 开始标记（优化：i*i 之前的已被更小的质数标记）// j 步进为 ifor (int j = i * i; j <= n; j += i) {isPrime[j] = false;}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n; cin>>n;// 预处理质数ePrime(n);int cnt=1; // 首先选择数1，计数为1for(int i=2; i<=n; i++){if(isPrime[i]) cnt++;}cout << cnt << endl;return 0;}
欧拉筛法:
#include<bits/stdc++.h>using namespace std;/** 贪心策略：* 为了从 1,2,…,n 中挑尽量多个数，使它们互质，只选质数和 1。* 问题则变成了统计1,2,…,n 里有多少个质数，答案再加 1*/// 质数三：欧拉筛法，标记质数（线性筛）bool isPrime[100010];vector<int> primes;voidoPrime(int n){// 初始化：全部设为 truefill(isPrime, isPrime + n + 2, true);isPrime[0] = isPrime[1] = false;// 欧拉筛核心for (int i = 2; i <= n; i++) {// 如果 i 是质数，加入质数列表primes.push_back(i);// 用质数列表去标记合数for (int j = 0; j < primes.size() && 1LL * i * primes[j] <= n; j++) {// 将 i * primes[j] 标记为合数isPrime[i * primes[j]] = false;// 核心：保证每个合数只被它的最小质因子标记if (i % primes[j] == 0) break;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n; cin>>n;// 预处理质数oPrime(n);cout << 1 + primes.size() << endl;return 0;}
↑微信扫码注册信奥公开课小程序↑
加 VX 联系年卡办理与备考资料领取
五级
STL模拟题解参考
完全模拟题意，喜提TLE
#include<bits/stdc++.h>using namespace std;int n, maxSize = 0;vector<int> bestSubset;// 检查新添加的数与当前集合中所有数是否互质boolcanAdd(int num, vector<int>& cur){for (int x : cur) {if (__gcd(x, num) != 1) {return false;}}return true;}voiddfs(int start, vector<int>& cur){// 更新最优解if (cur.size() > maxSize) {maxSize = cur.size();bestSubset = cur;}// 剪枝：即使把剩余所有数都加上也无法超过当前最优int remaining = n - start + 1;if (cur.size() + remaining <= maxSize) {return;}for (int i = start; i <= n; i++) {if (canAdd(i, cur)) {cur.push_back(i);dfs(i + 1, cur);cur.pop_back();}}}intmain(){cin >> n;vector<int> current;dfs(1, current);cout << maxSize << endl;// cout << "最优选择: {";// for (int i = 0; i < bestSubset.size(); i++) {// cout << bestSubset[i];// if (i < bestSubset.size() - 1) cout << ", ";// }// cout << "}" << endl;return 0;}
加 VX 联系年卡办理与备考资料领取
