最大乘积 - 优化拆分数字求最大乘积的算法

题目描述

一个正整数可以表示为若干个互不相同的正整数之和，例如 '6 = 1 + 5 = 2 + 4 = 1 + 2 + 3 = 6'，共有 4 种表示方法。这 4 种表示方法中，拆分出的数字的乘积分别为 5、8、6、6。

给定一个正整数 n，求 n 的所有表示方案中，拆分出的数字的乘积最大的方案，并按升序依次输出拆分出的数字。

输入格式

从标准输入读入数据。输入一个正整数 n (n ≤ 10^6)。

输出格式

输出到标准输出。按升序输出拆分出的数字。

样例 #1

样例输入 #1

样例输出 #1

2 4

样例 #2

样例输入 #2

样例输出 #2

2 3 5 6 7 8 9 10 11 12 13 14

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int primes[N], cnt;
bool st[N];

struct Node
{
    int p, q;
    bool operator< (const Node &t) const
    {
        if (p != t.p) return p < t.p;
        return q < t.q;
    }
}ans[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> n;

    get_primes(n);

    int cnt = 0;
    for (int i = 0; primes[i] <= n; i ++ )
        for (int j = primes[i]; j <= n; j *= primes[i])
            ans[cnt ++ ] = {primes[i], j};

    sort(ans, ans + cnt);

    int last = 0;
    for (int i = 0; i < cnt; i ++ )
        if (ans[i].p != last)
        {
            cout << ans[i].q << ' ';
            last = ans[i].p;
        }

    return 0;
}

算法解释

筛法求素数: 使用埃氏筛法获取 1 到 n 之间的素数，存储在 primes 数组中。
素数分解: 对于每个素数 primes[i]，将 n 不断除以 primes[i]，直到不能再除为止。每除一次，就将 primes[i] 和当前商加入到 ans 数组中。
结构体排序: 将 ans 数组中的元素按照 p 递增排序，若 p 相同则按照 q 递增排序，这将方便我们后面按照素数递增的顺序输出拆分出的数字。
遍历输出: 遍历 ans 数组，按照 p 的递增顺序，输出每个不同的 q，即为拆分出的数字。

优化分析

该算法使用了如下优化策略：

筛法求素数，避免了重复计算，提高了效率。
利用结构体存储素数和商，方便排序和遍历。
采用排序，保证输出结果的顺序。
遍历时只输出不同的素数，避免重复输出。

代码细节

st 数组用于标记是否为素数。
primes 数组存储所有素数。
ans 数组存储拆分出的数字，每个元素包含素数 p 和商 q。
get_primes 函数使用埃氏筛法获取素数。
main 函数中，循环遍历 primes 数组，并不断分解 n，将结果存储在 ans 数组中，最后对 ans 数组进行排序并输出。

总结

本文介绍了优化求解将一个正整数拆分成若干个互不相同的正整数之和，并使这些正整数乘积最大的算法。通过筛法求素数，将问题转化为素数分解，并利用结构体排序和遍历，高效地得到最优拆分方案。该算法的时间复杂度为 O(n log log n)，空间复杂度为 O(n)。