编程题
P14073 数字选取
【题目来源】
洛谷：P14073 [GESP202509 五级] 数字选取 - 洛谷
【题目描述】
给定正整数 \(n\)，现在有 \(1,2,…,n\) 共计 \(n\) 个整数。你需要从这 \(n\) 个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（也就是说，这两个整数的最大公因数为 \(1\)）。请你最大化所选取整数的数量。
例如，当 \(n=9\) 时，可以选择 \(1,5,7,8,9\) 共计 \(5\) 个整数。可以验证不存在数量更多的选取整数的方案。
【输入】
一行，一个正整数 \(n\)，表示给定的正整数。
【输出】
一行，一个正整数，表示所选取整数的最大数量。
【输入样例】
6
【输出样例】
4
【算法标签】
《洛谷 P14073 数字选取》 #数论# #素数判断,质数,筛法# #筛法# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100005; // 定义最大范围int n; // 输入的数字n
int isprime[N]; // 素数标记数组，isprime[i]存储i的最小质因数
map<int, int> mp; // 用于记录已经统计过的质因数int main()
{// 输入数字ncin >> n;// 埃拉托斯特尼筛法预处理最小质因数for (int i = 2; i < N; i++){// 如果i是素数，则标记其倍数if (isprime[i] == 0){for (int j = i + i; j < N; j += i){// 如果j还没有被标记过，则记录其最小质因数if (isprime[j] == 0){isprime[j] = i;}}}}// 统计1到n范围内的素数个数int cnt = 0;for (int i = 1; i <= n; i++){if (isprime[i] == 0){cnt++;}}// 统计1到n范围内合数的不同质因数个数for (int i = 1; i <= n; i++){// 如果是素数或者已经统计过该质因数，则跳过if (isprime[i] == 0 || mp[isprime[i]] == 1){continue;}// 标记该质因数已经统计过mp[isprime[i]] = 1;cnt++;}// 输出结果：素数个数 + 不同质因数个数cout << cnt << endl;return 0;
}
【运行结果】
6
4
P14074 有趣的数字和
【题目来源】
洛谷：P14074 [GESP202509 五级] 有趣的数字和 - 洛谷
【题目描述】
如果一个正整数的二进制表示包含奇数个 \(1\)，那么小 A 就会认为这个正整数是有趣的。
例如，\(7\) 的二进制表示为 \((111)_2\)，包含 \(1\) 的个数为 \(3\) 个，所以 \(7\) 是有趣的。但是 \(9=(1001)_2\) 包含 \(2\) 个 \(1\)，所以 \(9\) 不是有趣的。
给定正整数 \(l,r\)，请你统计满足 \(l≤n≤r\) 的有趣的整数 \(n\) 之和。
【输入】
一行，两个正整数 \(l,r\)，表示给定的正整数。
【输出】
一行，一个正整数，表示 \(l,r\) 之间有趣的整数之和。
【输入样例】
3 8
【输出样例】
19
【算法标签】
《洛谷 P14074 有趣的数字和》 #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型防止溢出int l, r; // 输入的数字区间[l, r]
int ans; // 存储计算结果
int b; // 计算第b个区间
int v[9] = {0, 1, 3, 3, 7, 7, 7, 14, 22}; // 预计算的小数值结果（1-8的答案）/*** 计算数字x的二进制表示中1的个数（汉明重量）* @param x 要计算的数字* @return 二进制中1的个数*/
int check(int x)
{int cnt = 0; // 计数器，记录1的个数while (x > 0){if (x & 1) // 检查最低位是否为1cnt++; // 如果是1，计数器加1x = x >> 1; // 右移一位，相当于除以2}return cnt;
}/*** 计算从1到x的所有满足条件的数的和* @param x 上界* @return 计算结果*/
int f(int x)
{// 如果x小于等于8，直接返回预计算的结果if (x <= 8)return v[x];// 计算区间个数（默认向下取整）b = x / 4;// 计算从第1到第b个区间的总和ans = (b * b) * 4 - b;// 计算剩余部分的值（从b*4到x）for (int i = (b * 4); i <= x; i++){// 如果二进制1的个数为奇数，则累加if (check(i) % 2)ans += i;}return ans;
}signed main()
{// 输入区间范围cin >> l >> r;// 输出区间内满足条件的数的和（前缀和思想）cout << f(r) - f(l - 1);return 0;
}
【运行结果】
3 8
19