大家好，我是энтджей，今天是我2026年第十一次正式发题解！

2026年发布的题解！

能不能点个赞

没有场切TAT

---

解题过程：

• 简化+分析题目：

  • 题意：

    • 其实就是第一句话：将正整数 n 拆分成若干个正整数之和，并最大化拆分后的正整数之积。

  • 复分析题目：

    • 经过测验发现规律：

      数字\其他	%3	超级拆解	最大化乘积
      1	1	1	1
      2	2	2	2
      3	0	3	3
      4	1	4	4
      5	2	3+2	6
      6	0	3+3	9
      7	1	3+2+2	12
      8	2	3+3+2	18
      9	0	3+3+3	27
      10	1	3+3+2+2	36
      ……	……	……	……

      不难发现：

$$MaxProduct(num) = \begin{cases} num ,num <= 4\\ 全部拆解成3的乘积,num \% 3 = 0\\ 先拆出两个2后，其余的拆解成3的乘积 ,num \% 3 = 1\\ 先拆出一个2后，其余的拆解成3的乘积,num \% 3 = 2\\ \end{cases}$$

代码实现：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int MOD = 1e9;
int T;
int n;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin >> T;
    while(T--){
        cin >> n;
        if(n <= 4){ //特别判断
            cout << n;
        } else if(n % 3 == 0){ //依据分析
            cout << (int)pow(3,n / 3) % MOD; 
        } else if(n % 3 == 1) {//依据分析
            cout << (int)pow(3,(n - 4) / 3) * 4 % MOD;
        } else { //依据分析
            cout << (int)pow(3,(n - 2) / 3) * 2 % MOD;
        }
        cout << endl;
    }
    return 0;
}

可以发现WA了一部分，进过观察，数据范围不允许这样写，会爆掉

---

优化解题过程：

• 关键点：

$$MaxProduct(num) = \begin{cases} num ,num <= 4\\ 全部拆解成3的乘积,num \% 3 = 0\\ 先拆出两个2后，其余的拆解成3的乘积 ,num \% 3 = 1\\ 先拆出一个2后，其余的拆解成3的乘积,num \% 3 = 2\\ \end{cases}$$

• 优化：

  • 依据关键点和数据范围，发现需要用快速幂来解决（化成二进制来进行计算）

优化后的代码实现（AC）：

#include<bits/stdc++.h>
#define int long long  
using namespace std;
const int MOD = 1e9;
const int N = 50;
int T;
int n;
int maxn = 1;
int FastPow(int num){ //快速幂
    int res = 1,p = 3;
    while(num){
        if(num & 1){
            res = (res * p) % MOD;
        }
        p = (p * p) % MOD;
        num >>= 1;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    
    cin >> T;
    while(T--){
        cin >> n;
        if(n <= 4){ //特别判断
            cout << n;
        } else if(n % 3 == 0){ //依据分析
            cout << (FastPow(n / 3)) % MOD;
        } else if(n % 3 == 1){ //依据分析
            cout << (FastPow((n - 4) / 3) * 4) % MOD;
        } else { //依据分析
            cout << (FastPow((n - 2) / 3) * 2) % MOD;
        }
        cout << endl;
    }
    return 0;
}

---

🎉完结撒花🎉