备战蓝桥杯国赛【Day 26】
一、写在前面
兄弟们，Day 26！今天刷的五道题全是硬核内容，数论和DP各占一半。素数筛、费马小定理求逆元、阶乘约数计数，这些数论知识点在国赛里经常出现；两道DP题分别用了滚动数组和线性递推，都是考场上必须掌握的优化技巧。
今天的五道题：
- 最大质因子个数 —— 素数筛+贪心
- 逆元 —— 费马小定理+快速幂
- 阶乘约数 —— 素数筛+约数定理
- 爬楼梯 —— 滚动数组DP
- 空位安排 —— 线性递推DP
二、第一题：最大质因子个数（难度：⭐⭐⭐）
2.1 题目大意
给定 n，求 n 最多能表示为多少个不同质数的乘积。换句话说，找最大的 k，使得前 k 个质数的乘积不超过 n。
2.2 解题思路
这题的思路很直接：
- 先用素数筛预处理出一定范围内的所有质数
- 从小到大依次乘上质数，直到乘积超过 n
- 统计乘了几个质数，就是答案
为什么这样是对的？因为要让质因子个数最多，每个质因子应该尽可能小，所以从小到大取质数是最优的。
2.3 代码实现
defselect(n):# 埃氏筛求素数primes=[True]*(n+1)primes[0]=primes[1]=Falsei=2whilei*i<=n:ifprimes[i]:forainrange(i*i,n+1,i):primes[a]=Falsei+=1return[ifori,binenumerate(primes)ifb]# 预处理100以内的质数（对于题目数据范围足够）primes=select(100)t=int(input())for_inrange(t):n=int(input())cur=1forjinrange(len(primes)):ifcur*primes[j]>n:print(j)breakcur*=primes[j]2.4 踩坑记录
- 素数筛的范围：100以内的质数足够应对大部分情况，前15个质数的乘积已经超过 10^17
- break的时机：当
cur * primes[j] > n时，说明不能再乘了，输出已经乘的个数 j - cur的更新：只有在能乘的情况下才更新
cur *= primes[j]
三、第二题：逆元（难度：⭐⭐⭐⭐）
3.1 题目大意
给定模数 M = 2146516019，求 1 到 233333333 中每个数的逆元的异或和。
3.2 解题思路
这道题考察费马小定理求逆元。
费马小定理：如果 p 是质数，且 a 不是 p 的倍数，那么a^(p-1) ≡ 1 (mod p)。
由此可得：a^(p-2) ≡ a^(-1) (mod p)，即 a 的逆元等于a^(p-2) mod p。
Python 的pow(a, p-2, p)可以直接用快速幂计算逆元，时间复杂度 O(log p)。
3.3 代码实现
mod=2146516019ans=0foriinrange(1,233333334):# 费马小定理求逆元：i^(M-2) mod Mans^=pow(i,mod-2,mod)%modprint(ans)3.4 踩坑记录
- pow的三参数形式：
pow(base, exp, mod)是Python内置的快速幂取模，效率很高 - 异或操作：
^=是按位异或，不是幂运算 - 模数是质数：费马小定理要求模数是质数，题目给出的 2146516019 确实是质数
- 数据范围：2亿多轮循环在Python里可能需要一些时间，但应该能在时限内跑完
四、第三题：阶乘约数（难度：⭐⭐⭐⭐）
4.1 题目大意
求 100! 的约数个数。
4.2 解题思路
约数个数定理：如果一个数 n 的质因数分解为n = p1^a1 * p2^a2 * ... * pk^ak，那么 n 的约数个数为(a1+1) * (a2+1) * ... * (ak+1)。
所以问题转化为：
- 找出 100 以内的所有质数
- 对每个质数 p，计算 100! 中 p 的指数（即 p 在 1 到 100 中出现多少次）
- 把所有 (指数+1) 相乘
计算 p 在 n! 中的指数：用勒让德公式vp(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...
不过这里数据范围小（100!），可以直接先算出 100!，然后对每个质数不断除取计数。
4.3 代码实现
importmath# 先算出100!n=math.factorial(100)defselect(n):# 埃氏筛primes=[True]*(n+1)primes[0]=primes[1]=Falsei=2whilei*i<=n:ifprimes[i]:forainrange(i*i,n+1,i):primes[a]=Falsei+=1return[ifori,binenumerate(primes)ifb]# 100以内的质数primes=select(100)ans=1foriinprimes:count=0# 计算100!中质数i的指数whilen%i==0:n//=i count+=1ans*=(count+1)print(ans)4.4 踩坑记录
- math.factorial：Python内置阶乘函数，可以直接用
- 勒让德公式：对于大数阶乘，应该先算指数再乘，而不是先算阶乘再分解（会溢出）
- 约数个数公式：每个质因子的指数要加1再相乘
- 数据类型：100! 非常大，但Python的整数可以任意精度，不用担心溢出
五、第四题：爬楼梯（难度：⭐⭐⭐）
5.1 题目大意
有一级 n 级的楼梯，每次可以跨1级或2级。但有 m 级台阶是坏掉的，不能踩。问从第0级爬到第 n 级的方案数。
5.2 解题思路
经典的爬楼梯问题的变形，加了坏台阶的限制。
状态转移：dp[i] = (dp[i-1] + dp[i-2]) * state[i]
dp[i]表示到达第 i 级的方案数state[i]表示第 i 级是否可用（1可用，0不可用）- 如果第 i 级不可用，
dp[i] = 0
用滚动数组优化空间，因为状态只依赖前两个。
5.3 代码实现
importosimportsys# 读取输入n,m=map(int,input().split())huai=list(map(int,input().split()))mod=10**9+7# 标记坏台阶state=[1]*(n+1)foriinhuai:state[i]=0# 滚动数组，只需要两个状态dp=[0]*2# 初始状态dp[0]=1# 第0级，1种方案（起点）dp[1]=1*state[1]# 第1级，取决于是否可用# 递推foriinrange(2,n+1):# dp[i%2] 表示当前状态# dp[(i-1)%2] 表示前一个状态# dp[(i-2)%2] 表示前两个状态dp[i%2]=(dp[(i-1)%2]+dp[(i-2)%2])*state[i]ans=dp[n%2]%modprint(ans)5.4 滚动数组原理
因为dp[i]只依赖dp[i-1]和dp[i-2]，所以不需要开 n+1 的数组，只需要两个位置来回倒腾：
i % 2和(i-1) % 2和(i-2) % 2的值在 0 和 1 之间循环- 这样空间复杂度从 O(n) 降到 O(1)
5.5 踩坑记录
- state数组：下标从0开始，第0级默认是好的（起点）
- 初始状态：
dp[0]=1表示起点，dp[1]要看第1级是否坏掉 - 取模：最后结果要取模，中间过程也要取模防止溢出
- 滚动数组下标：
i%2在 0 和 1 之间交替，注意对应关系
六、第五题：空位安排（难度：⭐⭐⭐⭐）
6.1 题目大意
有 n 个连续的空位，要安排一些长度为 k 的块。每个块占据 k 个连续空位，且块与块之间至少要隔1个空位。问有多少种安排方案。
6.2 解题思路
线性DP问题。设dp[i]表示前 i 个空位的方案数。
对于第 i 个空位：
- 不放块：方案数 =
dp[i-1] - 放块：从第 i-k+1 到第 i 放一个长度为 k 的块，前面至少要隔1个空位，所以方案数 =
dp[i-k-1]
状态转移：dp[i] = dp[i-1] + dp[i-k-1]
6.3 代码实现
mod=1000000007n,k=map(int,input().split())dp=[0]*(n+1)# 初始状态：0个空位也是一种方案（什么都不放）dp[0]=1foriinrange(1,n+1):ifi-k-1>=0:# 第i个空位：放块 + 不放块dp[i]=(dp[i-k-1]+dp[i-1])%modelse:# 空间不够放块，只能不放dp[i]=(1+dp[i-1])%modprint(dp[n])6.4 状态转移详解
以i - k - 1 >= 0为例：
- 不放块：前 i-1 个空位任意安排，
dp[i-1]种方案 - 放块：第 i-k+1 到 i 放一个块，前面至少隔1个空位，所以前 i-k-1 个空位任意安排，
dp[i-k-1]种方案 - 总方案数 = 两者之和
如果i - k - 1 < 0，说明空间不够放块，只能不放，方案数 =dp[i-1]。但代码里写了1 + dp[i-1]，这是因为dp[0]=1表示空安排，当 i=k 时，可以单独放一个块，也算1种方案。
6.5 踩坑记录
- 初始状态：
dp[0] = 1表示空安排也是一种方案 - 间隔要求：块与块之间至少隔1个空位，所以放块时要从前
i-k-1转移 - 边界条件：
i - k - 1 >= 0时才考虑放块的情况 - 取模：每一步都要取模，防止溢出
七、今日总结
| 题目 | 核心算法 | 关键技巧 | 易错点 |
|---|---|---|---|
| 最大质因子个数 | 素数筛+贪心 | 从小到大乘质数 | 素数筛范围、break时机 |
| 逆元 | 费马小定理 | pow快速幂 | 模数必须是质数 |
| 阶乘约数 | 约数定理 | 质因数分解 | 勒让德公式（大数用） |
| 爬楼梯 | 滚动数组DP | 空间优化 | state标记、初始状态 |
| 空位安排 | 线性DP | 放/不放两种状态 | 间隔处理、边界条件 |
今天这五道题覆盖了：
- 数论：素数筛、逆元、约数定理，这些都是国赛必考知识点
- 动态规划：滚动数组优化空间、线性递推，考场上能省则省
建议把素数筛的代码背熟，考场上直接默写。费马小定理求逆元也要记住公式和代码写法。DP题重点理解状态转移方程的推导过程。
明天继续肝真题，兄弟们一起加油！
相关知识点复习
- 素数算法：埃氏筛、欧拉筛、素数判定
- 数论定理：费马小定理、欧拉定理、约数定理、勒让德公式
- 动态规划：滚动数组、线性DP、状态设计
- 快速幂：
pow(a, b, mod)的用法
如果觉得有帮助，欢迎点赞收藏，有问题评论区见！