模拟与高精度:最大乘积

简介: 模拟与高精度:最大乘积

题目描述

一个正整数一般可以分为几个互不相同的自然数的和,如 3=1+2,4=1+35,=1+4=2+3,6=1+5=2+4。现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大。

输入格式  只一个正整数 n,(3≤n≤10000)。

输出格式第一行是分解方案,相邻的数之间用一个空格分开,并且按由小到大的顺序。第二行是最大的乘积。

输入输出样例

输入

10


输出

2 3 5

30

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
int n,a[1000],t;
struct bn{
  int len;
  int d[10000];
  bn() {
    memset(d, 0, sizeof(d));
    len = 0;
  }
};
bn mul(bn a, int b) {
  int carry = 0;
  bign res;
  for(int i = 0; i < a.len; i++) {
    int tem = a.d[i] * b + carry;
    res.d[res.len++] = tem % 10;
    carry = tem / 10;
  }
  while(carry) {
    res.d[res.len++] = carry % 10;
    carry /= 10;
  }
  while(res.len > 1 && res.d[res.len - 1] == 0) res.len--;
  return res;
}
void output(bn ans) {
  for(int i = ans.len - 1; i >= 0; i--)
    cout << ans.d[i];
  cout << endl;
}
int main() {
  cin >> n;
  if(n < 5) {
    cout << n;
    return 0;
  }
  int id = 2, sum = 0;
  while(n) {
    a[t++] = id;
    sum += id++;
    if(sum == n)
      break;
    if(sum > n) {
      if(sum == n + 1) {
        a[0] = 1;
        a[t - 1]++;
      }
      else {
        for(int i = 0; i < t; i++)
          if(a[i] == sum - n) {
            a[i] = 1;
            break;
          }
      }
      break;
    }
  }
  bn ans;
  ans.len = 1;
  ans.d[0] = 1;
  for(int i = 0; i < t; i++) {
    if(a[i] != 1)
      cout << a[i] << " ";
  }
  cout << endl;
  for(int i = 0; i < t; i++) {
    ans = mul(ans, a[i]);
  
  }
  output(ans);
  return 0;
}
目录
相关文章
|
7天前
本周练习题目(高精度,大数值)
本周练习题目(高精度,大数值)
|
29天前
|
存储 算法 索引
【算法基础】基础算法(二)--(高精度、前缀和、差分)(上)
【算法基础】基础算法(二)--(高精度、前缀和、差分)(上)
|
29天前
|
人工智能 算法 BI
【算法基础】基础算法(二)--(高精度、前缀和、差分)(下)
【算法基础】基础算法(二)--(高精度、前缀和、差分)(下)
|
1月前
|
算法 测试技术 C#
【矩阵】【方向】【素数】3044 出现频率最高的素数
【矩阵】【方向】【素数】3044 出现频率最高的素数
|
1月前
【每日一题Day153】LC2469温度转换 | 模拟
【每日一题Day153】LC2469温度转换 | 模拟
23 0
|
10月前
|
存储 人工智能 算法
【高精度加减乘除法、一维二维前缀和&&差分】思路讲解及代码实现
用一篇Blog来讲解下最近学到的高精度加减乘除法、一维二维前缀和&&差分等算法,为日后的刷题打下坚实的基础。
60 0
|
10月前
|
存储 人工智能 算法
【前缀和】截断数组、K倍区间、激光炸弹
现在,要将该数组从中间截断,得到三个非空子数组。
58 0
|
存储 算法 大数据
基础算法-高精度除法
高精度算法 为什么要使用高精度算法 C++ 每一个变量都有自己的类型,每个类型都有自己的存储长度范围。
|
存储 算法 大数据
基础算法-高精度减法
高精度算法 为什么要使用高精度算法 C++ 每一个变量都有自己的类型,每个类型都有自己的存储长度范围。
|
定位技术
(枚举)(模拟)(二位前缀和)99. 激光炸弹
(枚举)(模拟)(二位前缀和)99. 激光炸弹
62 0

热门文章

最新文章