题解：P1249 最大乘积

题目

题意

这道题的核心是将一个整数分解成若干个互不相同的自然数的和，并使得这些数的乘积最大。为了实现这一点，我们可以利用贪心策略，将数字尽可能拆成多个较小的数（从

2

开始递增），最后调整余数使乘积最大化。

解题思路：

拆分策略：
- 从 $2$ 开始逐步递增选取数字，直到总和接近目标值。
- 如果最后的和小于目标值，将剩下的差值从后往前分配给已选的数字。
高精度乘法：
- 由于最终乘积可能非常大，使用自定义的 BigInt 类进行高精度乘法运算。
- 每个数字存储为十进制数组，重载乘法运算符实现大数相乘。
输出结果：
- 输出拆分后的各个数。
- 计算它们的乘积并输出。

完整代码如下：

AC记录

CPP

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

struct BigInt {
    int digits[10000];
    int length;

    BigInt(int value = 0) {
        memset(digits, 0, sizeof(digits));
        if (value == 0) {
            length = 1;
            return;
        }
        for (length = 1; value; length++) {
            digits[length] = value % 10;
            value /= 10;
        }
        length--;
    }

    int& operator[](int index) {
        return digits[index];
    }

    void flatten(int maxLength) {
        length = maxLength;
        for (int i = 1; i <= length; ++i) {
            digits[i + 1] += digits[i] / 10;
            digits[i] %= 10;
        }
        while (length > 0 && digits[length] == 0) {
            --length;
        }
    }

    void print() {
        for (int i = max(length, 1); i >= 1; --i) {
            cout << digits[i];
        }
    }

    friend BigInt operator*(BigInt a, BigInt b) {
        BigInt result;
        int lenA = a.length, lenB = b.length;
        for (int i = 1; i <= lenA; ++i) {
            for (int j = 1; j <= lenB; ++j) {
                result[i + j - 1] += a[i] * b[j];
            }
        }
        result.flatten(lenA + lenB);
        return result;
    }
};

int main() {
    int target;
    int parts[10010];
    int partCount = 1;
    int currentNum = 2;
    int totalSum = 0;

    cin >> target;

    while (totalSum < target) {
        if (target - totalSum < currentNum) break;
        parts[partCount++] = currentNum;
        totalSum += currentNum;
        currentNum++;
    }

    int remaining = target - totalSum;

    while (remaining) {
        for (int i = partCount - 1; i >= 1 && remaining; --i) {
            parts[i] += 1;
            --remaining;
        }
    }

    for (int i = 1; i < partCount; ++i) {
        if (i != 1) cout << " ";
        cout << parts[i];
    }
    cout << endl;

    BigInt product(1);
    for (int i = 1; i < partCount; ++i) {
        product = product * parts[i];
    }

    product.print();
    cout << endl;

    return 0;
}

题解：P1249 最大乘积

文章操作

题目

题意

解题思路：

拆分策略：

高精度乘法：

输出结果：

完整代码如下：

AC记录

相关推荐

评论

题解：P1249 最大乘积