| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 117 人关注过本帖
标题:普及/提高−题目求助
只看楼主 加入收藏
夏天q
Rank: 4
来 自:七月
等 级:业余侠客
威 望:5
帖 子:36
专家分:227
注 册:2021-4-4
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:5 
普及/提高−题目求助
思考了很久,改了很多次代码,最后还是没能通过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
```
搜索更多相关主题的帖子: result for int sum size 
昨天 14:07
夏天q
Rank: 4
来 自:七月
等 级:业余侠客
威 望:5
帖 子:36
专家分:227
注 册:2021-4-4
收藏
得分:0 
图片附件: 游客没有浏览图片的权限,请 登录注册
题目截图
昨天 14:07
yiyanxiyin
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:9
帖 子:254
专家分:1910
注 册:2023-6-29
收藏
得分:0 
为什么要排除1
昨天 16:34
夏天q
Rank: 4
来 自:七月
等 级:业余侠客
威 望:5
帖 子:36
专家分:227
注 册:2021-4-4
收藏
得分:0 
回复 3楼 yiyanxiyin
因为要分解成最多个数因子相乘 才能使得结果最大 但是1是例外
昨天 16:47
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9034
专家分:54086
注 册:2011-1-18
收藏
得分:20 
看不懂你的算法,于是我重写了一个(没测试,仅供参考)

程序代码:
#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdint>
using namespace std;

struct BigInt
{
    BigInt& operator*=( unsigned n ) noexcept
    {
        uint_least64_t carry = 0;
        for( size_t i=0; i!=size_; ++i )
        {
            carry += uint_least64_t(n) * data_[i];
            data_[i] = carry%1000000000;
            carry /= 1000000000;
        }
        if( carry != 0 )
            data_[size_++] = (uint_least32_t)carry;
        return *this;
    }

    friend std::ostream& operator<<( std::ostream& os, const BigInt& b )
    {
        os << b.data_[b.size_-1];
        for( size_t i=b.size_-2; i!=size_t(-1); --i )
            os << setfill('0') << setw(9) << b.data_[i];
        return os;
    }

private:
    uint_least32_t data_[27] = { 1 }; // 每个存9个十进制位
    size_t size_ = 1;
};

int main( void )

{
    unsigned n;
    cin >> n;

    // 优先排列成 2 + 3 + 4 + ……
    // 若有剩余,均分给每一位
    // 若依然有剩余,从后往前再均分
    const unsigned m = (unsigned)floor( (sqrt(8*n+9)-3)/2 ); // 一共m项
    const unsigned c = n - (m+3)*m/2; // 余数
    BigInt sum;
    for( unsigned i=0; i!=m; ++i )
    {
        unsigned a =(i+2) + c/m + (i>=m-c%m );
        cout << a << " \n"[i+1==m];
        sum *= a;
    }
    cout << sum << endl;
}

输入 10000 的话,输出
2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
189814375907617096942852641411076779372817501189534937379724619699610191175976553324850685347478513897200254268291621670201923082029730482707591477173327806245278021157986072528028688788092832111659949431455744000000000000000000000000000000000
昨晚 22:13
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9034
专家分:54086
注 册:2011-1-18
收藏
得分:0 
2 + 3 + 4 + …… + (m+1) <= n
(m+3)*m/2 <= n
m^2 + 3m - 2n <= 0
m <= ( sqrt(8n+9) - 3 )/2

10000 = 2+3+4+……+9 + 11+12+13+……+141,积大约是 1.89814e+242
昨晚 22:14
快速回复:普及/提高−题目求助
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027093 second(s), 10 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved