题解：P15802 [GESP202603 七级] 拆分
Dustlpes_CZY
·
·
题解
前言
我常常追忆过去。
我们知道如果将一个数拆成两个数使其乘积最大，那这两个数最优就是相等或相差不大。
所以同周长下正方形面积比长方形大。
正文
运用到此题，对于样例有：
多试几个数，我们同样可以发现在 n > 3 时使用 3^x 乘上剩下一个 2 或 4 就可以达到最大值。
为什么呢？
我们可以思考思考，分出来的数只能是质数，因为合数可以被质数分解，而对于 n \le 3 时，它们自身就是最大值。所以我们就可以探讨 n > 3 时怎么解决了。
以 6 为例：6=2+2+2，而乘积是 2^3=8；但对于 3 而言：6=3+3，乘积是 3^2=9。
很明显 9 > 8。
所以这说明使用 3 比使用 2 分解 n 更好。
再来看以 21=3 \times 7=3 \times 6 +3 为例：
当然你也可以举其他栗子来说明，总之使用 $3$ 来分解 $n$ 是最优的。
~~这说明样例很重要。~~
得到这个结果我们就可以动手写了，吗？
看上上句话：样例很重要。因为我们前面举的例子都是 $n$ 能被 $3$ **整除**的！
如果多 $1$ 呢？根据样例得到，少乘一个 $3$ 改成乘 $4$ 呗。
多 $2$ 呢？~~根据样例得到，~~ 再乘个 $2$ 呗！
做完了，真的。
## [AC](https://www.luogu.com.cn/record/267544508) CODE
:::success[Code]
~~看来你还没学废。~~
```cpp
LL qow(LL x,LL y,LL res=1){
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod; y>>=1;
} the res;
}
//快速幂
//主函数部分:
if(n < 3) cout<<n<<"\n";
elif(n % 3 == 0) cout<<qow(3,n/3)<<"\n";
elif(n % 3 == 1) cout<<qow(3,n/3-1)*4%mod<<"\n";
else cout<<qow(n/3)*2%mod<<"\n";
```
:::
## 写在最后
声明：我的解法不一定正而且证明或许不太全面，~~因为本人是个蒟蒻~~相当于浅层理解，如果有其他大佬更强请看他们的佳作。对于我的，额，不喜勿盆，谢谢！
题解来之不易，审核题解不易，点个赞再走吧！！！
管理员大大辛苦了！！！