2026年3月GESP真题及题解（C++七级）：拆分

2026年3月GESP真题及题解C七级拆分题目描述小 A 想将正整数n nn拆分成若干个正整数之和并最大化拆分后的正整数之积。小 A 希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大你只需要求出答案对10 9 10^9109取模的结果。形式化地n nn的拆分是满足a 1 ⋯ a k n a_1\cdotsa_kna1​⋯ak​n的若干个正整数a 1 , … , a k a_1,\dots,a_ka1​,…,ak​其中1 ≤ k ≤ n 1\leq k\leq n1≤k≤n。你需要求出n nn的所有拆分中a 1 × ⋯ × a k a_1\times \cdots\times a_ka1​×⋯×ak​的最大值对10 9 10^9109取模的结果。输入格式第一行一个正整数t tt表示数据组数。对于每组数据一行一个整数n nn表示给定的正整数。输出格式对于每组数据输出一行一个整数表示n nn拆分后正整数之积的最大值对10 9 10^9109取模的结果。输入输出样例 1输入 13 5 8 100输出 16 18 755407364说明/提示对于40 % 40\%40%的测试点保证n ≤ 50 n\leq 50n≤50。对于所有测试点保证1 ≤ t ≤ 10 4 1\leq t\leq 10^41≤t≤1041 ≤ n ≤ 10 6 1\leq n\leq 10^61≤n≤106。思路分析本题要求将正整数n nn拆分成若干个正整数之和使得这些正整数的乘积最大并输出该最大值对10 9 10^9109取模的结果。这是一个经典的整数拆分问题其最优策略是尽量多地使用3 33作为拆分因子因为3 33能在保持和不变的情况下使乘积最大化。具体推导如下当n ≤ 4 n \le 4n≤4时不拆分即只用一个数n nn得到的乘积最大因此答案就是n nn本身。当n ≥ 5 n \ge 5n≥5时将n nn写成n 3 a r n 3a rn3ar其中a ⌊ n / 3 ⌋ a \lfloor n/3 \rfloora⌊n/3⌋r n m o d 3 r n \bmod 3rnmod3。根据余数r rr的不同最优拆分方案为若r 0 r 0r0则全部拆成3 33乘积为3 a 3^a3a。若r 1 r 1r1则将最后一个3 33与1 11合并成两个2 22因为3 × 1 2 × 2 3 \times 1 2 \times 23×12×2即拆成a − 1 a-1a−1个3 33和两个2 22乘积为3 a − 1 × 4 3^{a-1} \times 43a−1×4。若r 2 r 2r2则拆成a aa个3 33和一个2 22乘积为3 a × 2 3^a \times 23a×2。由于n nn最大可达10 6 10^6106且最多有10 4 10^4104组数据直接计算3 33的幂会非常大因此需要使用快速幂取模模数为10 9 10^9109。代码实现#includebits/stdc.husingnamespacestd;constintmod1e9;// 模数 10^9// 快速幂函数计算 a^b % modintqp(inta,intb){intr1;// 结果初始化为 1while(b){// 当指数 b 不为 0 时循环if(b1)// 如果 b 的二进制最低位为 1r1ll*r*a%mod;// 将当前底数乘入结果并取模a1ll*a*a%mod;// 底数平方准备下一位b1;// 指数右移一位}returnr;}intmain(){ios::sync_with_stdio(false);// 加速输入输出cin.tie(nullptr);intt;// 数据组数cint;while(t--){intn;// 当前要拆分的数cinn;intans;// 存储答案if(n4){// n ≤ 4 时不拆分就是最优ansn%mod;}else{intan/3;// 3 的个数intrn%3;// 余数if(r0){// 余数为 0全部用 3ansqp(3,a);}elseif(r1){// 余数为 1将 31 换成 22// 此时 a ≥ 1因为 n ≥ 5ans4ll*qp(3,a-1)%mod;}else{// 余数为 2加一个 2ans2ll*qp(3,a)%mod;}}coutans\n;// 输出答案并换行}return0;}功能分析算法核心基于数学推导的贪心策略将n nn尽量拆分为3 33并根据余数调整。时间复杂度为O ( t log ⁡ n ) O(t \log n)O(tlogn)其中log ⁡ n \log nlogn是快速幂的复杂度对于n ≤ 10 6 n \le 10^6n≤106最多约 20 次运算可以轻松应对10 4 10^4104组数据。取模处理所有乘法均使用1ll*转换为 64 位整数防止溢出并即时对10 9 10^9109取模确保答案在合法范围内。边界情况对n ≤ 4 n \le 4n≤4进行了特判避免了后续计算中可能出现的负指数如r 1 r1r1时a − 1 a-1a−1可能为负。代码简洁性使用单字母变量名和极简函数名符合题目要求输入输出经过优化保证速度。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整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;}