求方程a₁X₁+a₂X₂+…+aₙXₙ=M的正整数解个数：代码问题排查

给定两个正整数n、M和n个正整数a₁,a₂,…,aₙ，需要统计方程 a₁X₁+a₂X₂+…+aₙXₙ=M 的正整数解的个数。编写了如下C++递归代码，但运行时输出遗漏部分解；若改用数组u[]替代m0则会出现多余解，请求排查问题。

#include <bits/stdc++.h>

using namespace std;

int n, m;
int res = 0;
int f = 0, p = 0;  // f = Sum(ai*Xi): (1<=i<=k-1); p = Sum(ai): (k+1<=i<=n)
// f is the remaining part after subtracting the part under consideration, p is the part to ensure that each unexamined element is >= 1.
int m0;     // m0 is max of x[k]; m0=(m-f-p)/ak
const int MAXN = 100;
int A[MAXN], x[MAXN];

void Try(int k)
{
    if (k == n)   
    {
        if ((m0-f) % A[k] == 0)  
        {
            x[k] = (m0-f) / A[k];
            res++;
        }
        return;
    }
    m0 = (m - f - p) / A[k];
    if (m0 >= 1)
        for (int v = 1; v <= m0; v++)
        {
            x[k] = v;
            f=f+A[k]*v;
            p=p-A[k+1];
            Try(k + 1);
            f=f-A[k]*v;
            p=p+A[k+1];
        }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = 2; i <= n; i++)
        p += A[i];
    Try(1);
    cout << res << endl;
    return 0;
}

核心问题点 #

1. 全局变量m0的覆盖问题
   m0是全局变量，递归过程中会被上层调用覆盖。当进入k==n的终止逻辑时，m0存储的是k=n-1层计算的最大值，无法正确约束第n个变量的取值，导致部分合法解被遗漏。

2. 终止条件逻辑错误
   终止时用(m0-f) % A[k] == 0判断，本质是用前一层的约束来验证当前层，完全不符合正整数解的要求。正确的逻辑应该是：剩余数值m-f必须能被A[n]整除，且得到的结果是正整数。

3. 递归参数维护的隐含风险
   全局变量f和p在递归回溯时虽然做了还原，但全局状态的共享容易因为逻辑疏忽出现错误，比如p的更新仅针对A[k+1]，当k接近n时可能出现越界或计算偏差。

修正后的代码 #

#include <bits/stdc++.h>

using namespace std;

int n, m;
int res = 0;
const int MAXN = 100;
int A[MAXN];

void Try(int k, int current_sum, int min_remaining) {
    // current_sum: 已选变量的累加和（1~k-1）
    // min_remaining: 未选变量的最小和（每个变量至少取1，即A[k]+...+A[n]）
    if (k == n) {
        int remaining = m - current_sum;
        // 剩余值必须能被A[n]整除，且结果为正整数
        if (remaining >= A[n] && remaining % A[n] == 0) {
            res++;
        }
        return;
    }
    // 计算当前变量x[k]的最大取值：保证剩余变量至少能取1
    int min_next = min_remaining - A[k];
    int max_v = (m - current_sum - min_next) / A[k];
    // 遍历x[k]的所有合法正整数值
    for (int v = 1; v <= max_v; v++) {
        Try(k + 1, current_sum + A[k] * v, min_next);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
    }
    // 先判断最小和是否超过m，直接排除无解情况
    int total_min = 0;
    for (int i = 1; i <= n; i++) {
        total_min += A[i];
    }
    if (total_min > m) {
        cout << 0 << endl;
        return 0;
    }
    Try(1, 0, total_min);
    cout << res << endl;
    return 0;
}

修正说明 #

• 移除全局变量，改用递归参数传递current_sum和min_remaining，避免状态覆盖问题；
• 终止条件直接验证剩余值是否符合第n个变量的正整数要求；
• 前置判断最小和是否超过m，提前返回无解结果，减少无效递归；
• 每一层的变量最大值计算严格保证剩余变量能取到正整数，避免出现多余解。

内容的提问来源于stack exchange，提问作者Bùi Anh Đức