※ 引述《initial13254 (瑟约)》之铭言：
: 以前有上过一个算法的课
: 有一个很鸟的作业
: 题目是有个老板想送人冬瓜砖 共N个 冬瓜砖长宽高10公分
: 他想用包装纸这些冬瓜砖 而且包装起来要
:
: 1.包装成一个x*y*z的长方体
: 2.包装纸越少越好
: 3.不能有空隙
:
: 一旦N是质数例如19 你包装起来必定是一个190*10*10的超长超细长方体
: 虽然我觉得题目可能有少打什么或有错误 不过课本上面就是这么写的
:
: 起初并没有什么难 但随者数字越来越大 就越不知道怎么设计
: 当N是4个质数相乘之前我都还行 5个质数相乘我就炸了
: 开始乱瞎猜 什么开立方根阿 先乘个3看看阿 反正跟数学逻辑没什么关系了
:
: 最后老师上课讲解告诉我 : 题目好像怪怪的 只好用暴力破解法喔啾咪
: 推 e5a1t20: 满足正整数xyz=N，求xy+xz+zy最小，只求表面积还是包装 12/10 21:07
: → e5a1t20: 纸还要长方形把冬瓜砖包起来？ 12/10 21:07
: → e5a1t20: 求最小N/x+xN/k+k，让k=xy，这样算起来暴力解的复杂度大 12/10 21:25
: → e5a1t20: 概比N的因子数量^2小 12/10 21:25
我刚刚在看角卷绵芽昨天的SC时候想到这问题
https://pbs.twimg.com/media/EoUJcfJUYAE8uhJ.jpg
这个算法问题其实还满有趣的啊
假设我们考虑一个比较广泛的问题：
给定两个整数 N 和 n，
求所有满足 x_1*x_2*....x_n = N 的正整数组合 (x_1,x_2,...,x_n) 中，
n
Σ N/x_i 的最小值
i=1
原来的那个包装问题就是这问题在 n=3 的特例
假设给定两整数N,n所能得到的最小值是 f(N,n)，则我们有
f(N,n) = min N/u + u*f(N/u, n-1)
u | N (意即u是N的因子)
f(N,1) = 1
f(1,n) = n
这作法时间复杂度是 o( (N的因子数量)^2*n )
硬爆我觉得就算用backtracking在n稍大都会炸开来

摁摁 我想也是这样

为什么会在看羊的时候想到啊…

不就尻完的时候开始思考宇宙的真理吗

想了一下 所以要先对N做质因子分解 并将N的质因子任意分为三组数组 并且确保三组乘积的标准差为最小吧？

推贤者XD 这分析漂亮 受教了