简单分解-最优分解贪心问题

简单分解-最优分解贪心问题

题目描述

现有一个数 n n n，需要把n分解成一个或多个两两互不相同的正整数（例如： 9 9 9可以分解成 2 、 3 、 4 2、3、4 2、3、4，也可以分解成 4 、 5 4、5 4、5，但不能分解成 1 、 2 、 3 、 3 1、2、3、3 1、2、3、3。当然也可以不分解，这样 9 9 9能分解的结果中累乘的最大值是 24 24 24），并累乘，累乘结果最大值可能是多少。

输入描述:

多组输入，每组一个正整数 n ， ( 1 ≤ n ≤ 1 0 5 ) n，(1≤n≤10^5) n，(1≤n≤105)

输出描述:

输出一个整数，表示分解后累乘的最大值，结果对 1 0 9 + 7 10^9+7 109+7取模。

问题分析

首先，此类问题均属于最有分解问题。

我们首先关注整数的一个性质：若 a + b = N a + b =N a+b=N(常数)，则 ∣ a − b ∣ | a - b | ∣a−b∣越小， a × b a \times b a×b越大

证明： a + b = N a + b = N a+b=N，则有 ( a − b ) 2 = a 2 + a a b + b 2 = ( a + b ) 2 − 4 a b = N 2 − 4 a b (a -b) ^ 2 = a ^2 + aab + b^2 = (a + b) ^ 2 - 4ab = N^2 -4ab (a−b)2=a2+aab+b2=(a+b)2−4ab=N2−4ab

则 a b = N 2 − ( a − b ) 2 4 = N 2 − ∣ a − b ∣ 2 4 ab = \frac {N^2 - (a - b)^2}{4} = \frac {N^2 - |a - b|^2}{4} ab=4N2−(a−b)2​=4N2−∣a−b∣2​，显然 ∣ a − b ∣ |a - b| ∣a−b∣越小， a × b a \times b a×b越大。

由于 a × b = N 2 − ∣ a − b ∣ 2 4 a \times b = \frac {N^2 - |a - b|^2}{4} a×b=4N2−∣a−b∣2​，那么我们需要对 N N N进行分类讨论：

1. 当 N < 4 N < 4 NN >N
2. 如果最后剩下的数字小于前一个，就要平均分配给前面的数字，且要从后往前分，反之可能会产生重复数字

将 N N N 分成从 2 2 2 开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。该贪心策略首先保证了正整数所分解出的因子之差的绝对值最小，即 ∣ a – b ∣ | a – b | ∣a–b∣最小；同时又可以将其分解成尽可能多的因子，且因子的值较大，确保最终所分解的自然数的乘积可以取得最大值 。

#include 
using namespace std;

#define Max 100005
int main(){
    int n; cin >> n;
    if (n