整数分拆使乘积最大

发表于 分类于 阅读次数：

POJ 1032 是一个数论问题：给定一个正整数 \(n \geq 5\)，求一个整数数列 \(A = (a_1,a_2, \cdots, a_k)\)，满足 \(\sum_i a_i = n\) 和 \(0 < a_1 < a_2 < \cdots < a_k\)，且 \(\prod_i a_i\)最大。

\(A\) 有以下性质：
1. \(a_1 > 1\)，因为 \(1 \cdot a_i < 1 + a_i\)
2. \(a_1 \leq 3\)，因为如果 \(a_1 > 3, a_1 \cdot a_2 < 2 \cdot (a_1 - 1) \cdot (a_2 - 1)\)
3. 项数尽可能多，因为 \(2 \leq a_p < a_q, a_p + a_q < a_p \cdot a_q\)

猜想 \(A\) 的形式接近 \(T = (2, 3, \cdots, m)\)。
记 \(T(m) = \sum_{i=2}^m i = \frac{m(m+1)}{2} - 1\)，存在唯一的 \(m = \lfloor \frac{\sqrt{8n+9} - 1}{2} \rfloor\) 使得 \(T(m) \leq n < T(m+1)\)。设 \(n = T(m) + l, 0 \leq l \leq m\)。

用\(\{T\}\)表示数列\(T\)的各项组成的有序集合，即 \(\{T\} = \{2, 3, \cdots, m\}\)。
Maximum Product Over Partitions Into Distinct Parts 这篇论文证明了所求数列（用集合表示）为 \[ \{A\} = \begin{cases} \{T\} & , & l = 0\\ \{T\} - \{2\} + \{m+2\} & , & l = m\\ \{T\} - \{m-l+1\} + \{m+1\} & , & 1 \leq l \leq m-1 \end{cases} \] 数列长度为 \(m-1\)。即将 \(l\) 个1分别加到 \(T\) 的倒数 \(l\) 项，其中 \(l = m\) 时多出一个1加到最后一项。

C++代码实现如下。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cmath>
#include <set>

int main() {
    int n, m, Tm, l;
    std::set<int> A;
    std::cin >> n;

    m = static_cast<int> ((sqrt(8 * n + 9) - 1) / 2.0);
    Tm = m * (m + 1) / 2 - 1;
    l = n - Tm;

    for (int i = 2; i <= m; ++i) {
        A.insert(i);
    }

    if (l > 0) {
        if (l == m) {
            A.erase(2);
            A.insert(m + 2);
        } else {
            A.erase(m - l + 1);
            A.insert(m + 1);
        }
    }

    for (auto el : A) {
        std::cout << el << ' ';
    }

    return 0;
}

Update

发现 ZOJ 2037 是同一题，不过输入包含多个 case。
ZOJ 支持 Python。我有点好奇 Python 比 C/C++ 慢多少，于是提交了以下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from math import sqrt
from sys import stdin, stdout


def part(n):
    m = int((sqrt(8 * n + 9) - 1) / 2)
    tm = m * (m + 1) // 2 - 1
    l = n - tm
    a = list(range(2, m + 1))
    if l > 0:
        if l == m:
            del a[0]
            a.append(m + 2)
        else:
            del a[m - l - 1]
            a.append(m + 1)
    return ' '.join(map(str, a))


data = map(int, stdin.read().split()[1:])
stdout.write('\n\n'.join(part(x) for x in data))

结果是 AC，Time 0 ms，Memory 144 KB。咦，排在 C 前面？
然而我再重复了几次，Time 都是 10 ms。看来不用太纠结那么多 0 ms 怎么来的～

相关问题

附件