csp信奥赛C++之反素数

csp信奥赛C之反素数原题说明洛谷P1463 反素数题目描述对于任何正整数x xx其约数的个数记作g ( x ) g(x)g(x)。例如g ( 1 ) 1 g(1)1g(1)1g ( 6 ) 4 g(6)4g(6)4。如果某个正整数x xx满足∀ 0 i x \forall 0 \lt i \lt x∀0ix都有g ( x ) g ( i ) g(x) \gt g(i)g(x)g(i)则称x xx为反素数。例如1 , 2 , 4 , 6 , 12 , 24 1,2,4,6,12,241,2,4,6,12,24等都是反素数。现在给定一个正整数N NN你能求出不超过N NN的最大的反素数么输入格式仅一行一个正整数N NN。输出格式仅一行一个正整数代表不超过N NN的最大的反素数。输入输出样例 1输入 11000输出 1840说明/提示对于所有数据有1 ≤ N ≤ 2 × 10 9 1 \leq N \leq 2 \times 10^91≤N≤2×109。思路分析1. 反素数的定义与性质定义一个正整数x xx是反素数当且仅当对于任意i x i xix都有g ( x ) g ( i ) g(x) g(i)g(x)g(i)g ( x ) g(x)g(x)表示x xx的约数个数。直观理解反素数就是在所有不超过它的数中拥有最多约数个数的那个数。因此反素数一定是“高度合成数”但还必须保证前面没有数能与之持平或超过。2. 约数个数的计算公式若x xx的质因数分解为x p 1 a 1 p 2 a 2 ⋯ p k a k x p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}xp1a1​​p2a2​​⋯pkak​​则其约数个数为g ( x ) ( a 1 1 ) ( a 2 1 ) ⋯ ( a k 1 ) g(x) (a_11)(a_21)\cdots(a_k1)g(x)(a1​1)(a2​1)⋯(ak​1)3. 反素数必须满足的两个重要性质性质一质因子必须是连续的最小质数假设x xx是一个反素数如果它的质因子集合不是从 2 开始连续的前k kk个质数比如缺少质数p j p_jpj​却包含了更大的质数p t p_tpt​那么我们可以用p j p_jpj​替换p t p_tpt​保持指数不变得到一个新的数x ′ x x xx′x但g ( x ′ ) g ( x ) g(x) g(x)g(x′)g(x)。这与反素数的定义矛盾因为存在更小的数有相同的约数个数。因此反素数的质因子一定是从 2 开始的连续质数2 , 3 , 5 , 7 , … 2,3,5,7,\dots2,3,5,7,…。性质二指数单调不增非递增假设x 2 a 1 3 a 2 ⋯ p k a k x 2^{a_1}3^{a_2}\cdots p_k^{a_k}x2a1​3a2​⋯pkak​​是反素数若存在a i a i 1 a_i a_{i1}ai​ai1​即指数递增那么交换这两个指数得到x ′ 2 a 1 ⋯ p i a i 1 p i 1 a i ⋯ x 2^{a_1}\cdots p_i^{a_{i1}}p_{i1}^{a_i}\cdotsx′2a1​⋯piai1​​pi1ai​​⋯。由于p i p i 1 p_i p_{i1}pi​pi1​交换后x ′ x x xx′x但约数个数不变因为指数集合相同。同样存在更小的数有相同约数个数矛盾。因此指数必须满足a 1 ≥ a 2 ≥ ⋯ ≥ a k ≥ 1 a_1 \ge a_2 \ge \cdots \ge a_k \ge 1a1​≥a2​≥⋯≥ak​≥1。4. 基于性质的搜索算法利用上述两条性质所有可能的反素数候选都可以通过**深度优先搜索DFS**枚举指数组合得到并且可以大幅剪枝。搜索框架质数表由于N ≤ 2 × 10 9 N \le 2\times10^9N≤2×109我们只需考虑前几个质数。2 × 3 × 5 × 7 × 11 × 13 × 17 × 19 × 23 × 29 ≈ 6.13 × 10 9 2\times3\times5\times7\times11\times13\times17\times19\times23\times29\approx 6.13\times10^92×3×5×7×11×13×17×19×23×29≈6.13×109已经超过N NN所以前 10 个质数足够。DFS 状态cur当前构造的数值。cnt当前约数个数根据公式累乘。last上一个质数使用的指数当前质数的指数不能超过它满足性质二。pos当前考虑第几个质数从 0 开始。搜索过程每到达一个状态首先检查是否需要更新答案若cnt mx历史最大约数个数则更新答案和最大值。若cnt mx且cur ans数值更小也更新答案因为反素数要求数值本身最小。然后尝试为下一个质数p[pos]分配指数i ii从 1 到last枚举注意指数至少为 1。累乘new_cur cur * p[pos]^i但实际采用迭代乘法防止幂运算开销。如果new_cur N则停止枚举更大的指数剪枝。递归调用dfs(new_cur, cnt*(i1), i, pos1)。初始调用dfs(1, 1, 31, 0)。cur1cnt1g ( 1 ) 1 g(1)1g(1)1。last初始设为一个很大的数31因为第一个质数 2 的指数理论上限可达⌊ log ⁡ 2 N ⌋ \lfloor \log_2 N \rfloor⌊log2​N⌋而2 31 2 × 10 9 2^{31}2\times10^92312×109所以 31 足够大相当于“无限”。pos0表示从质数 2 开始。5. 算法的正确性完备性所有可能的指数组合满足指数非递增都会被搜索到因为递归树遍历了所有合法的指数分配。由于质数连续且指数单调每个反素数必然对应一条搜索路径。剪枝的正确性当当前乘积超过N NN时后续更大指数或更大质数的乘积必定更大因此可以直接剪枝不会遗漏任何不超过N NN的候选数。最优性在搜索过程中我们时刻用全局变量ans和mx记录当前最优值。由于搜索顺序指数从大到小枚举保证了先遇到的可能是较小数值但最终通过比较更新可以确保得到的是不超过N NN的最大反素数即约数个数最多且数值最小。6. 时间复杂度分析状态总数非常有限。对于N 2 × 10 9 N2\times10^9N2×109指数组合的数目大约在几千量级实际测试中递归次数不超过 5000因此算法可以在毫秒级内完成。AC代码#includebits/stdc.husingnamespacestd;typedeflonglongll;// 质数表前10个质数因为2*3*5*7*11*13*17*19*23 ≈ 2.2e8再乘29 ≈ 6.3e9 2e9constintp[]{2,3,5,7,11,13,17,19,23,29};intn;// 输入上限ll ans1;// 当前答案初始为1intmx1;// 当前最大约数个数g(1)1// 深搜cur 当前乘积cnt 当前约数个数last 上一质数的指数pos 当前质数下标voiddfs(ll cur,intcnt,intlast,intpos){// 更新答案约数个数更大 或 相等但数值更小if(cntmx||(cntmxcurans)){mxcnt;anscur;}// 没有更多质数可选if(pos10)return;ll tmpcur;// 用于累乘// 枚举当前质数 p[pos] 的指数 i从1到last并保证乘积不超过nfor(inti1;ilast;i){tmp*p[pos];if(tmpn)break;// 超出范围停止枚举更大的指数dfs(tmp,cnt*(i1),i,pos1);}}intmain(){cinn;dfs(1,1,31,0);// last初始设为一个很大的数31足以覆盖2^312e9coutansendl;return0;}功能分析以 (N10) 为例我们详细分析 DFS 算法的执行过程。算法利用反素数的性质质因子连续且指数非递增枚举所有可能的数并动态更新最优解约数个数最多且数值最小。初始状态质数表p[] {2,3,5,7,11,13,17,19,23,29}只需前几个全局变量ans 1当前答案mx 1当前最大约数个数初始调用dfs(1, 1, 31, 0)参数说明当前乘积cur1约数个数cnt1上一指数last31足够大当前质数下标pos0对应质数2递归树展开第一层质数 2在dfs(1,1,31,0)中更新答案cnt1与mx1相等且cur1等于ans不更新。枚举指数i从 1 开始累乘cur并确保不超过N10i1cur 1*2 2调用dfs(2, 1*(11)2, last1, pos1)i2cur 2*2 4调用dfs(4, 1*(21)3, last2, pos1)i3cur 4*2 8调用dfs(8, 1*(31)4, last3, pos1)i4cur 8*2 16 10停止。第二层处理各个分支分支 Adfs(2,2,1,1)当前质数 3更新答案cnt2 mx1→ 更新ans2, mx2枚举质数 3 的指数i从 1 到last1i1cur 2*3 6调用dfs(6, 2*(11)4, last1, pos2)分支 A1dfs(6,4,1,2)当前质数 5更新答案cnt4 mx2→ 更新ans6, mx4枚举质数 5 的指数i从 1 到last1i1cur 6*5 30 10停止。返回分支 Bdfs(4,3,2,1)当前质数 3更新答案cnt3 mx4不更新枚举质数 3 的指数i从 1 到last2i1cur 4*3 12 10停止后续更大指数更不可能返回分支 Cdfs(8,4,3,1)当前质数 3更新答案cnt4 mx4但cur8 ans6不更新枚举质数 3 的指数i从 1 到last3i1cur 8*3 24 10停止返回最终结果所有递归结束后全局变量ans6mx4输出6。正确性验证不超过 10 的正整数中约数个数最多为 4对应的数有 6、8、10。其中 6 是最小的且所有小于 6 的数的约数个数均小于 4因此 6 是反素数。算法通过 DFS 遍历了所有可能的候选满足质数连续且指数非递增并正确选出了最优解。算法要点每次进入 DFS 即检查更新保证任何新数都被考虑。利用质数连续和指数非递增性质大幅剪枝避免无效枚举。当乘积超过 N 时立即停止确保只搜索合法范围。【文末福利一等奖秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}