GESP认证C++编程真题解析 | 202603 七级

张开发
• 2026/4/5 10:46:46 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

GESP认证C++编程真题解析 | 202603 七级
编程题P15802 拆分【题目来源】洛谷[P15802 GESP202603 七级] 拆分 - 洛谷【题目描述】小 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取模的结果。【输入样例】3 5 8 100【输出样例】6 18 755407364【解题思路】【算法标签】《洛谷 P15802 拆分》 #动态规划DP# #数学# #贪心# #分类讨论# #GESP# #2026#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN4000005,mod1e9;intt,n,ans[6]{0,1,2,3,4,6};// 小规模n的答案// 快速幂取模intqmi(inta,intb){intmul1;while(b){if(b1){mulmul*a%mod;}aa*a%mod;b1;}returnmul;}signedmain(){cint;while(t--){cinn;if(n6)// n较小直接查表{coutans[n]endl;}elseif(n%30)// n是3的倍数{coutqmi(3,n/3)endl;// 全部分成3}elseif(n%31)// 余数为1{// 将最后一个4分成31不如分成22所以是3^(k-1)*4cout(qmi(3,n/3-1)*4)%modendl;}else// 余数为2{// 分成若干个3和一个2cout(qmi(3,n/3)*2)%modendl;}}return0;}【运行结果】3 5 6 8 18 100 755407364

更多文章