正整数N的4个除数和为N且乘积最大的递归实现求助

给定正整数N，找到四个均为N的除数的整数A、B、C、D，满足N = A + B + C + D。若存在多组解，需找出乘积(ABC*D)最大的一组；若无符合条件的四元组，输出-1。同时支持处理t个不同N的测试用例。

你当前的递归代码无法正确更新最大值MXN，核心问题如下：

1. 参数传递错误：solve函数中的MXN是按值传递，递归内部修改的是局部副本，不会影响主函数中的MXN变量，导致主函数始终输出初始值-1。
2. 递归逻辑冗余：从索引0开始遍历除数，会生成大量重复的四元组（如[1,1,2,4]和[1,2,1,4]），增加不必要的计算量。
3. 未处理边界情况：当N<4时，四个正整数的和最小为4，不可能满足条件，可直接输出-1，无需进入递归。

以下是修复上述问题后的代码，同时优化了递归逻辑以避免重复组合，并使用long long防止乘积溢出：

#include <bits/stdc++.h>
using namespace std;

// start参数控制从当前索引开始选数，避免生成重复组合
void solve(int n, const vector<int>& dv, vector<int>& v, int start, long long& max_product) {
    if (v.size() == 4) {
        int sum = 0;
        long long product = 1;
        for (int num : v) {
            sum += num;
            product *= num;
        }
        if (sum == n && product > max_product) {
            max_product = product;
        }
        return;
    }
    for (int i = start; i < dv.size(); ++i) {
        v.push_back(dv[i]);
        solve(n, dv, v, i, max_product); // 允许重复选当前除数
        v.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        if (n < 4) {
            cout << "-1\n";
            continue;
        }
        // 收集所有小于n的除数（n本身无法参与组成和为n的四元组）
        vector<int> dv;
        dv.push_back(1);
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                dv.push_back(i);
                if (i != n / i) {
                    dv.push_back(n / i);
                }
            }
        }
        sort(dv.begin(), dv.end());
        long long max_product = -1;
        vector<int> v;
        solve(n, dv, v, 0, max_product);
        cout << max_product << "\n";
    }
    return 0;
}

递归枚举所有组合在N较大、除数较多时效率较低。利用数学性质：当和固定时，数值越接近，乘积越大，可以优先检查乘积最大的可能情况，无需遍历所有组合：

1. 四个相等的数：若N能被4整除，且N/4是N的除数（即N是4的倍数），则四个数均为N/4，乘积为(N/4)^4，这是最优解。
2. 三个相等的数：寻找除数d，使得N-3*d也是N的除数且大于0，计算d^3*(N-3*d)，记录最大值。
3. 两对相等的数：若N是偶数，寻找除数d≤e，满足d+e=N/2，计算(d*e)^2，记录最大值。
4. 两个相等+两个不同的数：寻找除数d，再找除数e≤f满足2*d+e+f=N，计算d^2*e*f，记录最大值。
5. 四个不同的数：寻找四个不同的除数d<e<f<g满足和为N，计算乘积并记录最大值。

最终从所有候选值中取最大的，若无候选则输出-1。这种方法大幅减少了计算量，尤其适合大N的场景。

内容的提问来源于stack exchange，提问作者the.modest.guy