普及/提高−题目求助
思考了很久,改了很多次代码,最后还是没能通过OJ系统程序代码:
#include <bits/stdc++.h> using namespace std; struct BigInt { vector<int> digits; void removeLeadingZeros() { } BigInt() {}; BigInt(int n) { while (n) { digits.push_back(n % 10); n /= 10; } } friend ostream &operator<<(ostream &os, const BigInt &bigInt) { for (auto it = bigInt.digits.rbegin(); it != bigInt.digits.rend(); ++it) { os << *it; } return os; } BigInt operator*(const BigInt &other) const { BigInt result; result.digits.resize(digits.size() + other.digits.size(), 0); for (int i = 0; i < digits.size(); ++i) { int carry = 0; for (int j = 0; j < other.digits.size() || carry; ++j) { long long prod = result.digits[i + j] + (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) + carry; result.digits[i + j] = prod % 10; carry = prod / 10; } } result.removeLeadingZeros(); return result; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); int n; cin >> n; BigInt res(1); int sum = 0; map<int, bool> mp; for (int i = 2; i <= n; ++i) { sum += i; if (sum > n) { if (mp[sum - n]) { mp[sum - n] = false; mp[i] = true; sum = n; } else { sum -= i; } } else if (sum < n) { mp[i] = true; } if (sum == n) { for (const auto &[a, b] : mp) { if (b) { cout << a << " "; res = res * BigInt(a); } } cout << endl << res << endl; break; } } return 0; }
以下是题目
# 最大乘积P1249
## 题目描述
一个正整数一般可以分为几个互不相同的自然数的和,如 $3=1+2$,$4=1+3$,$5=1+4=2+3$,$6=1+5=2+4$。
现在你的任务是将指定的正整数 $n$ 分解成若干个互不相同的自然数(也可以不分解,就是这个数字本身)的和,且使这些自然数的乘积最大。
## 输入格式
只一个正整数 $n$,($3 \leq n \leq 10000$)。
## 输出格式
第一行是分解方案,相邻的数之间用一个空格分开,并且按由小到大的顺序。
第二行是最大的乘积。
## 样例 #1
### 样例输入 #1
```
10
```
### 样例输出 #1
```
2 3 5
30
```