当前位置：首页 > news >正文

备战蓝桥杯国赛【Day 22】

news 2026/6/1 4:27:47

一、写在前面

兄弟们，Day 22！今天搞了一套第十三届蓝桥杯国赛的真题，把前四道题全部过了一遍。不得不说，国赛的难度确实比省赛高了一个档次，尤其是填空题，如果硬算的话时间根本不够，必须找规律。大题部分考察的知识点也很综合，涉及质数筛、数论推导、字符串解析等。

今天的四道题：

斐波那契与7 —— 找规律+周期
小蓝做实验 —— 质数筛+大数判断
取模 —— 数论推导+反证法
内存空间 —— 字符串解析+模拟

二、第一题：斐波那契与7（难度：⭐⭐⭐）

2.1 题目大意

斐波那契数列：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。问前 202202011200 项中，有多少项的个位数字是7？

2.2 解题思路

这题数据量巨大（2022亿项），直接递推肯定超时，必须找规律。

关键观察：个位数字只跟个位数字有关。比如 13+24=37，个位只由 3+4=7 决定。所以斐波那契数列的个位数字序列也是有周期的。

我们只需要模拟前若干项的个位，找到周期即可。

2.3 代码实现

a,b=1,1num=2ans=0# 找规律：只考虑个位whilenum<=180:cur=(a+b)%10# 只保留个位a,b=b,curifcur==7:ans+=1num+=1# 打印出来看看规律# num ans# 60 8# 120 16# 180 24# 发现规律：60个循环一组，每组有8个7print(202202011200//60*8)

2.4 规律验证

手动模拟一下个位序列：

F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=3, F(8)=1…
个位序列：1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8,7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1,0,1,1…

数一下，前60项里有8个7。而且因为只跟个位有关，这个周期会一直重复下去。

所以答案 = 202202011200 // 60 * 8 = 26960268160

2.5 踩坑记录

不要硬算：2022亿项，Python也跑不动，必须找周期。
只保留个位：cur = (a + b) % 10，这样数字不会越界。
周期验证：多跑几组确认周期确实是60，不要只看一组就下结论。

三、第二题：小蓝做实验（难度：⭐⭐⭐⭐）

3.1 题目大意

给定一个文件primes.txt，里面有很多数字。判断其中有多少个是质数。数字范围很大，有些可能超过 10^8。

3.2 解题思路

这题分两部分处理：

小于等于 10^8 的数：用埃氏筛预处理所有质数，然后 O(1) 判断
大于 10^8 的数：直接试除法判断（因为这类数不会太多）

埃氏筛的时间复杂度是 O(n log log n)，对于 10^8 来说在Python里有点悬，但实际测试可以通过。

3.3 代码实现

f=open('primes.txt','r',encoding='utf-8')txt=f.read().split()# 按位数分开处理arr1=[int(i)foriintxtiflen(i)<=8]# 小于等于10^8arr2=[int(i)foriintxtiflen(i)>8]# 大于10^8# 埃氏筛defselects(n):primes=[True]*(n+1)primes[0]=primes[1]=Falsep=2whilep*p<=n:ifprimes[p]:foriinrange(p*p,n+1,p):primes[i]=Falsep+=1returnprimes n=10**8ans=0prime=selects(n)# 小于等于10^8的数，直接查表foriinarr1:ifprime[i]:ans+=1# 大于10^8的数，试除法判断foriinarr2:is_prime=Trueforjinrange(2,int(i**0.5)+1):ifi%j==0:is_prime=Falsebreakifis_prime:ans+=1print(ans)

3.4 踩坑记录

埃氏筛的内存：10^8 的布尔数组大概占 100MB，要注意内存限制。
试除法优化：只需要判断到 sqrt(n) 即可，不要傻乎乎地遍历到 n。
文件读取：f.read().split()可以直接按空白字符分割，不用一行行读。
大数处理：大于 10^8 的数如果很多，试除法会超时，但这题数据量应该不大。

四、第三题：取模（难度：⭐⭐⭐⭐）

4.1 题目大意

给定 n 和 m，问是否存在两个不同的数 x, y（1 ≤ x < y ≤ m），使得 n mod x = n mod y。

4.2 解题思路

这题如果暴力枚举 x 和 y，时间复杂度是 O(m²)，对于大数会超时。需要用数论推导。

关键思路：反证法。假设不存在这样的 x 和 y，那么对于所有 1 ≤ x < y ≤ m，都有 n mod x ≠ n mod y。

这意味着 n mod 1, n mod 2, …, n mod m 这 m 个余数互不相同。

但余数的范围是 0 到 x-1，所以：

n mod 1 = 0（唯一可能的值）
n mod 2 必须是 1（因为0已经被占了）
n mod 3 必须是 2
…
n mod m 必须是 m-1

也就是说，如果存在解，必须满足 n % i == i - 1 对所有 i ∈ [1, m] 成立。

反过来，只要存在一个 i 使得 n % i ≠ i - 1，就一定存在解。

4.3 代码实现

importsysinput=sys.stdin.readline T=int(input())for_inrange(T):n,m=map(int,input().split())flag=Trueforiinrange(1,m+1):ifn%i!=i-1:print('Yes')# 存在这样的x,yflag=Falsebreakifflag:print('No')# 不存在

4.4 证明过程

为什么 n % i = i - 1 对所有 i 成立时，就不存在解？

因为如果 n % i = i - 1，那么 n + 1 能被 i 整除（因为 n = k*i + (i-1)，所以 n+1 = (k+1)*i）。

也就是说 n + 1 是 1, 2, …, m 的公倍数。只有当 n + 1 是 lcm(1,2,…,m) 的倍数时才可能。

对于一般的 n 和 m，这种情况几乎不可能发生，所以大部分情况下答案都是 “Yes”。

4.5 踩坑记录

不要暴力：O(m²) 的暴力在 m 很大时会超时，必须推导数学规律。
反证法的逻辑：想清楚"不存在解"的充要条件是什么。
边界情况：m=1 时，不存在两个不同的数，直接输出 “No”。

五、第四题：内存空间（难度：⭐⭐⭐⭐）

5.1 题目大意

给定一段类似 C/C++ 的代码，统计其中声明的变量占用的总内存空间。涉及三种类型：

int：占 4 字节
long：占 8 字节
String：字符串类型，每个字符占 1 字节（不算引号）

变量声明格式：

int a=1,b=2;—— 普通变量，每个占 4 字节
int arr[10];—— 数组，占 4*10 = 40 字节
int arr[10][20];—— 多维数组，占 41020 = 800 字节
String s="hello";—— 字符串，占 5 字节
String s="hello",t="world";—— 多个字符串

最后把总字节数转换成人类可读格式（B/KB/MB/GB），每 1024 进一位。

5.2 解题思路

这题是字符串解析+模拟。需要逐行解析代码，识别变量类型，计算每种变量占用的空间。

核心逻辑：

判断类型（int/long/String）
判断是否是数组（看有没有[]）
如果是数组，解析维度并计算元素个数
如果是普通变量，统计=的个数（每个=对应一个变量）
如果是 String，解析引号内的字符数

5.3 代码实现

importosimportsys t=int(input())ans=0for_inrange(t):k=0cur=0s=input().strip()ifs[0]=='i':# int 类型k=4ifs[3:5]=='[]':# 是数组s=s[5:]# 解析多维数组的维度whiles.find('[')!=-1:st=s.find('[')+1ed=s.find(']')cur+=int(s[st:ed])s=s[ed+1:]ans+=k*curelse:# 普通变量# 统计 = 的数量，每个 = 对应一个变量whiles.find('=')!=-1:cur+=1s=s[s.find('=')+1:]ans+=k*curelifs[0]=='l':# long 类型k=8ifs[4:6]=='[]':# 是数组s=s[6:]whiles.find('[')!=-1:st=s.find('[')+1ed=s.find(']')cur+=int(s[st:ed])s=s[ed+1:]ans+=k*curelse:# 普通变量whiles.find('=')!=-1:cur+=1s=s[s.find('=')+1:]ans+=k*curelse:# String 类型whiles.find('=')!=-1:# 找到双引号的位置st=s.find('"')+1ifs.find(',')!=-1:ed=s.find(',')-1else:ed=s.find(';')-1ans+=ed-st s=s[ed+2:]# 转换成人类可读格式dans=['B','KB','MB','GB']st=''pos=0whileans!=0:ifans%1024!=0:st=str(ans%1024)+dans[pos]+st ans//=1024pos+=1print(st)

5.4 踩坑记录

数组维度解析：多维数组如arr[10][20]，需要循环解析每个[]里的数字，然后相乘。
int 和 long 的区别：int后面数组从第3位开始判断（int[]），long从第4位开始（long[]）。
String 的引号：是英文双引号"，不是中文引号，解析时要注意。
多个变量：int a=1,b=2;这种一行多个变量的情况，要通过统计=的数量来判断变量个数。
单位转换：每 1024 进一位，从 B -> KB -> MB -> GB，注意是除法取余的方式转换。

六、今日总结

题目	核心算法	关键技巧	易错点
斐波那契与7	找规律	个位周期	不要硬算大数
小蓝做实验	质数筛+试除	埃氏筛预处理	内存限制、大数处理
取模	数论推导	反证法	暴力会超时
内存空间	字符串解析	正则/字符串操作	数组维度、引号类型