2026年3月GESP真题及题解（C++七级）：拆分
题目描述
小 A 想将正整数 
拆分成若干个正整数之和，并最大化拆分后的正整数之积。小 A 希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对 
取模的结果。
形式化地，
的拆分是满足 
的若干个正整数 
，其中 
。你需要求出 
的所有拆分中 
的最大值对 
取模的结果。
输入格式
第一行，一个正整数 
，表示数据组数。
对于每组数据：一行，一个整数 
，表示给定的正整数。
输出格式
对于每组数据：输出一行，一个整数，表示 
拆分后正整数之积的最大值对 
取模的结果。
输入输出样例 1
输入 1
358100
输出 1
618755407364
说明/提示
对于 
的测试点，保证 
。
对于所有测试点，保证 
，
。
思路分析
本题要求将正整数 
拆分成若干个正整数之和，使得这些正整数的乘积最大，并输出该最大值对 
取模的结果。这是一个经典的整数拆分问题，其最优策略是尽量多地使用 
作为拆分因子，因为 
能在保持和不变的情况下使乘积最大化。具体推导如下：
当 
时，不拆分（即只用一个数 
）得到的乘积最大，因此答案就是 
本身。当 
时，将 
写成 
，其中 
，
。根据余数 
的不同，最优拆分方案为： 若 
，则全部拆成 
，乘积为 
。若 
，则将最后一个 
与 
合并成两个 
（因为 
），即拆成 
个 
和两个 
，乘积为 
。若 
，则拆成 
个 
和一个 
，乘积为 
。
由于 
最大可达 
，且最多有 
组数据，直接计算 
的幂会非常大，因此需要使用快速幂取模，模数为 
。
代码实现
#include<bits/stdc++.h>using namespace std;const int mod = 1e9; // 模数 10^9// 快速幂函数，计算 a^b % modintqp(int a, int b){int r = 1; // 结果初始化为 1while (b) { // 当指数 b 不为 0 时循环if (b & 1) // 如果 b 的二进制最低位为 1r = 1ll * r * a % mod; // 将当前底数乘入结果并取模a = 1ll * a * a % mod; // 底数平方，准备下一位b >>= 1; // 指数右移一位}return r;}intmain(){ios::sync_with_stdio(false); // 加速输入输出cin.tie(nullptr);int t; // 数据组数cin >> t;while (t--) {int n; // 当前要拆分的数cin >> n;int ans; // 存储答案if (n <= 4) { // n ≤ 4 时，不拆分就是最优ans = n % mod;} else {int a = n / 3; // 3 的个数int r = n % 3; // 余数if (r == 0) { // 余数为 0，全部用 3ans = qp(3, a);} else if (r == 1) { // 余数为 1，将 3+1 换成 2+2// 此时 a ≥ 1，因为 n ≥ 5ans = 4ll * qp(3, a - 1) % mod;} else { // 余数为 2，加一个 2ans = 2ll * qp(3, a) % mod;}}cout << ans << '\n'; // 输出答案并换行}return 0;}
功能分析
- 算法核心
：基于数学推导的贪心策略，将 
尽量拆分为 
，并根据余数调整。时间复杂度为 
，其中 
是快速幂的复杂度，对于 
最多约 20 次运算，可以轻松应对 
组数据。 - 取模处理
：所有乘法均使用 1ll*转换为 64 位整数防止溢出，并即时对
取模，确保答案在合法范围内。 - 边界情况
：对 
进行了特判，避免了后续计算中可能出现的负指数（如 
时 
可能为负）。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>using namespace std;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return 0;}
【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437
3、csp信奥赛高频考点知识详解及案例实践：
信奥赛C++提高组csp-s高频考点知识详解（视频课）：https://edu.csdn.net/course/detail/41081
CSP信奥赛C++动态规划：https://blog.csdn.net/weixin_66461496/category_13096895.html
CSP信奥赛C++标准模板库STL：https://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
· 文末祝福 ·
#include<bits/stdc++.h>using namespace std;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return 0;}
