|
#2
夏天q5 天前 14:07
|
程序代码：#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;
}
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
```
