题解：P1249 最大乘积

· · 题解

题目

题意

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

解题思路：

  1. 拆分策略：

    • 从 2 开始逐步递增选取数字，直到总和接近目标值。
    • 如果最后的和小于目标值，将剩下的差值从后往前分配给已选的数字。

  2. 高精度乘法：

    • 由于最终乘积可能非常大，使用自定义的 BigInt 类进行高精度乘法运算。
    • 每个数字存储为十进制数组，重载乘法运算符实现大数相乘。

  3. 输出结果：

    • 输出拆分后的各个数。
    • 计算它们的乘积并输出。

      完整代码如下：

      AC记录

      
#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;

}