第十三届蓝桥杯大赛软件赛决赛（Java 大学C组）

蓝桥杯 2022年国赛真题
^{Java 大学C组}

• 试题 A: 斐波那契与 7
• 试题 B: 小蓝做实验
• 试题 C: 取模
• 试题 D: 内存空间
• 试题 E: 斐波那契数组
• 试题 F: 最大公约数
• 试题 G: 交通信号
• 试题 H: 点亮
• 试题  I: 打折
• 试题 J: 宝石收集

试题 A: 斐波那契与 7

本题总分：$5$ 分

【问题描述】

??斐波那契数列的递推公式为$：$$F_n=F_{n?1}+F_{n?2}$，其中 $F_1=F_2=1$。

??请问，斐波那契数列的第 $1$ 至 $202202011200$ 项（含）中，有多少项的个位是 $7$。

【答案提交】

??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

26960268160

找循环节

??找到斐波那契数列在个位上的循环节，然后将答案拆分成三部分就完事了。

试题 B: 小蓝做实验

本题总分：$5$ 分

【问题描述】

??小蓝很喜欢科研，他最近做了一个实验得到了一批实验数据，一共是两百万个正整数。如果按照预期，所有的实验数据 $x$ 都应该满足 $10^7\le x\le 10^8$。但是做实验都会有一些误差，会导致出现一些预期外的数据，这种误差数据 $y$ 的范围是 $10^3\le y\le 10^{12}$ 。由于小蓝做实验很可靠，所以他所有的实验数据中 $99.99\%$ 以上都是符合预期的。小蓝的所有实验数据都在 $primes.txt$ 中，现 在他想统计这两百万个正整数中有多少个是质数，你能告诉他吗/p>

【答案提交】

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

342693

欧拉筛

??首先排除 $\mathrm{Miller}$–$\mathrm{Robin}$，一般 $T$ 次询问的题目，$T$ 越大，对单次询问响应的复杂度要求越高，于是考虑欧拉筛线性筛出不大于 $1e8$ 的质数，$O(1)$ 响应 $99.99\%$ 的询问，而剩下询问中，$y$ 不会大于 $1e16$，利用因数的对称性，可以在 $O(\sqrt{y}$