备战蓝桥杯国赛【Day 26】

一、写在前面兄弟们Day 26今天刷的五道题全是硬核内容数论和DP各占一半。素数筛、费马小定理求逆元、阶乘约数计数这些数论知识点在国赛里经常出现两道DP题分别用了滚动数组和线性递推都是考场上必须掌握的优化技巧。今天的五道题最大质因子个数 —— 素数筛贪心逆元 —— 费马小定理快速幂阶乘约数 —— 素数筛约数定理爬楼梯 —— 滚动数组DP空位安排 —— 线性递推DP二、第一题最大质因子个数难度⭐⭐⭐2.1 题目大意给定 n求 n 最多能表示为多少个不同质数的乘积。换句话说找最大的 k使得前 k 个质数的乘积不超过 n。2.2 解题思路这题的思路很直接先用素数筛预处理出一定范围内的所有质数从小到大依次乘上质数直到乘积超过 n统计乘了几个质数就是答案为什么这样是对的因为要让质因子个数最多每个质因子应该尽可能小所以从小到大取质数是最优的。2.3 代码实现defselect(n):# 埃氏筛求素数primes[True]*(n1)primes[0]primes[1]Falsei2whilei*in:ifprimes[i]:forainrange(i*i,n1,i):primes[a]Falsei1return[ifori,binenumerate(primes)ifb]# 预处理100以内的质数对于题目数据范围足够primesselect(100)tint(input())for_inrange(t):nint(input())cur1forjinrange(len(primes)):ifcur*primes[j]n:print(j)breakcur*primes[j]2.4 踩坑记录素数筛的范围100以内的质数足够应对大部分情况前15个质数的乘积已经超过 10^17break的时机当cur * primes[j] n时说明不能再乘了输出已经乘的个数 jcur的更新只有在能乘的情况下才更新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 代码实现mod2146516019ans0foriinrange(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 的约数个数为(a11) * (a21) * ... * (ak1)。所以问题转化为找出 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!nmath.factorial(100)defselect(n):# 埃氏筛primes[True]*(n1)primes[0]primes[1]Falsei2whilei*in:ifprimes[i]:forainrange(i*i,n1,i):primes[a]Falsei1return[ifori,binenumerate(primes)ifb]# 100以内的质数primesselect(100)ans1foriinprimes:count0# 计算100!中质数i的指数whilen%i0:n//i count1ans*(count1)print(ans)4.4 踩坑记录math.factorialPython内置阶乘函数可以直接用勒让德公式对于大数阶乘应该先算指数再乘而不是先算阶乘再分解会溢出约数个数公式每个质因子的指数要加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,mmap(int,input().split())huailist(map(int,input().split()))mod10**97# 标记坏台阶state[1]*(n1)foriinhuai:state[i]0# 滚动数组只需要两个状态dp[0]*2# 初始状态dp[0]1# 第0级1种方案起点dp[1]1*state[1]# 第1级取决于是否可用# 递推foriinrange(2,n1):# dp[i%2] 表示当前状态# dp[(i-1)%2] 表示前一个状态# dp[(i-2)%2] 表示前两个状态dp[i%2](dp[(i-1)%2]dp[(i-2)%2])*state[i]ansdp[n%2]%modprint(ans)5.4 滚动数组原理因为dp[i]只依赖dp[i-1]和dp[i-2]所以不需要开 n1 的数组只需要两个位置来回倒腾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-k1 到第 i 放一个长度为 k 的块前面至少要隔1个空位所以方案数 dp[i-k-1]状态转移dp[i] dp[i-1] dp[i-k-1]6.3 代码实现mod1000000007n,kmap(int,input().split())dp[0]*(n1)# 初始状态0个空位也是一种方案什么都不放dp[0]1foriinrange(1,n1):ifi-k-10:# 第i个空位放块 不放块dp[i](dp[i-k-1]dp[i-1])%modelse:# 空间不够放块只能不放dp[i](1dp[i-1])%modprint(dp[n])6.4 状态转移详解以i - k - 1 0为例不放块前 i-1 个空位任意安排dp[i-1]种方案放块第 i-k1 到 i 放一个块前面至少隔1个空位所以前 i-k-1 个空位任意安排dp[i-k-1]种方案总方案数 两者之和如果i - k - 1 0说明空间不够放块只能不放方案数 dp[i-1]。但代码里写了1 dp[i-1]这是因为dp[0]1表示空安排当 ik 时可以单独放一个块也算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)的用法如果觉得有帮助欢迎点赞收藏有问题评论区见