题解：洛谷 P15802 [GESP202603 七级] 拆分

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：P15802 [GESP202603 七级] 拆分 - 洛谷

【题目描述】

小 A 想将正整数n nn拆分成若干个正整数之和，并最大化拆分后的正整数之积。小 A 希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对10 9 10^9109取模的结果。

形式化地，n nn的拆分是满足a 1 + ⋯ + a k = n a_1+\cdots+a_k=na1​+⋯+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

【解题思路】

【算法标签】

#普及# #快速幂#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=4000005,mod=1e9;intt,n,ans[6]={0,1,2,3,4,6};// 小规模n的答案// 快速幂取模intqmi(inta,intb){intmul=1;while(b){if(b&1){mul=mul*a%mod;}a=a*a%mod;b>>=1;}returnmul;}signedmain(){cin>>t;while(t--){cin>>n;if(n<6)// n较小，直接查表{cout<<ans[n]<<endl;}elseif(n%3==0)// n是3的倍数{cout<<qmi(3,n/3)<<endl;// 全部分成3}elseif(n%3==1)// 余数为1{// 将最后一个4分成3+1不如分成2+2，所以是3^(k-1)*4cout<<(qmi(3,n/3-1)*4)%mod<<endl;}else// 余数为2{// 分成若干个3和一个2cout<<(qmi(3,n/3)*2)%mod<<endl;}}return0;}

【运行结果】

3 5 6 8 18 100 755407364