[特殊字符] 2025蓝桥杯备赛Day11——P11041 [蓝桥杯 2024 省 Java B] 报数游戏

🔍 2025蓝桥杯备赛Day11——P11041 [蓝桥杯 2024 省 Java B] 报数游戏

🚀 题目速览

题目难度：⭐️⭐️⭐️（需要数论与二分法结合）

考察重点：容斥原理、二分搜索、最小公倍数计算

（当然也可以直接用数学知识做题，判断并记录偶数次数，24 * 2 * 偶数次数，也就是暴力枚举，代码好像不行，用excel）

题目描述

小蓝和朋友们在玩一个报数游戏。由于今年是 $2024$ 年，他们决定要从小到大轮流报出是 $20$ 或 $24$ 倍数的正整数。前 $10$ 个被报出的数是： $20, 24, 40, 48, 60, 72, 80, 96, 100, 120$ 。请问第 $202420242024$ 个被报出的数是多少？

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只输出这个整数，填写多余的内容将无法得分。

输入格式

本题无输入。

输出格式

一行一个整数，表示你算出的答案。

🔥 解法：暴力枚举

🛠️ 实现思路

核心逻辑：

从小到大遍历每个正整数
检查当前数是否为20或24的倍数
统计满足条件的数直到找到第N个

缺陷：

时间复杂度为 O(K)（K为最终结果值），当N=2e12时完全不可行
仅适用于极小的N值（如N≤1e5）

#include<bits/stdc++.h>
using namespace std;
long long N = 202420242024;int main(){// 计算从1到N的偶数数量long long count = 0;for(int i=1;i<=N;i++){if(N%2==0) count++; 	}// 根据提供的公式计算nlong long n = 2 * count * 24;// 输出n=2429042904288cout << n << endl;return 0;
}

🔥 最优解法：二分法 + 容斥原理

🛠️ 实现思路

核心数学工具：

容斥原理：计算范围内20或24的倍数的总数
二分法：快速定位第N个数的值

关键公式：

 count(x) = x//20 + x//24 - x//120

其中120是20和24的最小公倍数（LCM）。

代码实现

#include <iostream>
#include <numeric>  // 包含gcd函数
using namespace std;
using ll = long long;int main() {const ll N = 202420242024LL;ll low = 1, high = 20 * N;  // 初始二分边界const ll lcm_20_24 = 20 * 24 / gcd(20, 24);  // LCM(20,24)=120while (low < high) {ll mid = low + (high - low) / 2;  // 防止溢出ll cnt = mid/20 + mid/24 - mid/lcm_20_24;if (cnt < N) low = mid + 1;  // 不足目标数量，抬高下界else high = mid;             // 满足条件，压低上界}cout << low;  // 输出结果return 0;
}

📚 核心知识点解析

一、容斥原理应用

项	计算方式	说明
20的倍数数量	`x // 20`	每20个数出现一次
24的倍数数量	`x // 24`	每24个数出现一次
公倍数数量	`x // 120`	120是LCM(20,24)=120
有效总数	`20倍 + 24倍 - 公倍数`	避免重复计数

二、二分法优化

步骤	操作	时间复杂度
初始化边界	`low=1`, `high=20*N`	O(1)
二分循环	每次将搜索范围减半	O(logN)
最终定位	当`low==high`时即为答案	O(1)

三、暴力枚举的局限性

维度	说明
时间复杂度	O(K)（K≈2e12时需数十年计算）
内存消耗	O(1)
适用场景	仅用于教学演示或极小的N值（如N≤1e5）

🚨 易错点警示

LCM计算错误

# 错误：直接相乘未除GCD
lcm = 20 * 24  # 得到480（正确应为120）
# 正确计算方式
from math import gcd
lcm = 20 * 24 // gcd(20, 24)

二分边界设置不足

Pythonhigh = 20 * n  # 可能不够大
# 安全设置
high = 2 * 10**30  # 足够覆盖所有可能情况

🔥 双解法对比分析

维度	二分法（解法二）	暴力枚举（解法一）
时间复杂度	O(logN)（约40次循环）	O(K)（无法完成N=2e12的计算）
空间复杂度	O(1)	O(1)
适用数据规模	任意规模（推荐）	仅限N≤1e5
工程价值	竞赛标准解法	仅用于教学展示
实现难度	需理解数论原理	逻辑简单但无法实际应用