所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物...

dxxbjl

题：
> 有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。现规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
规定所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n=L×W×H。
当 n=4 时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1
当 n=2021041820210418 （注意有 16位数字）时，总共有多少种方案？

思路1：

常规解法 三层循环暴力求解
long n = 2021041820210418l;

    int count = 0;
    for ( long H = 1 ; H < n ; H++ ){
        for ( long W = 1 ; W < n ; W++ ){
            for ( long H = 1 ; H < n ; H++ ){
                if ( L * W *H ){
                    count++;
                }
            }
        }
    }

//由于num过大，暴力循环需要好几天才能出结果，舍弃

思路2、

因为LWH = n ,所以L、W、H都是n的因数，可以先求出n有多少个因子，然后在因子中循环，减少循环范围
n= 2021041820210418 具有16位，用long类型

long n = 2021041820210418l;
int count=0;
//起初不知道有多少个因子，先定义个list放因子
ArrayList<Long> list =new ArrayList<>(); 

//for循环中的变量i 为long类型；因为是因子，所以是相乘的形式，为了节省时间，只求开平方数之前
for(long i=1l;i<Math.sqrt(n);i++) { 
    //求因子，如果能整除就是因子
    if(n % i == 0) {
    //如果是因子，则放入list
    list.add(i);
    //j是n的另外一个因子，即开平方数之后的数
    long j = n / i; 
        //当j不等于i的时候，把j也放入list，防止放重了
        if(n!=i) {
        list.add(j);
        }
    } 
}
//System.out.println(list.size());//打印看一下长度 = 128，可以暴力循环

 for (Long L : list) {
    for (Long W : list) {
        for (Long H : list) {
            if(L*W*H == n) {
                count++;
            }
        }
    }
}
System.out.println(count); //2430
//运行耗时809ms<1s 可行

//for循环
/*
 for (int L = 0; L < list.size(); L++) {
    for (int W = 0; W < list.size(); W++) {
        for (int H = 0; H < list.size(); H++) {
            if(list.get(L)* list.get(W) *list.get(H) == n) {
                count++;
            }
        }
    }
}
System.out.println(count); //2430
for循环中如果定义的LWH为long 类型，list.get(int index) index类型是int
*/

永恒陌

emmmmm。

永恒陌

永恒陌 发表于 2023-3-17 11:39
emmmmm。

chatgpt如是说：
这是一个组合数学问题，需要用到数学知识进行计算。

由于每个货物都是正方体，因此可以将它们想象成小立方体，每个小立方体的边长都为1。现在要将这些小立方体堆成一个大的长方体，总共需要n个小立方体，因此大的长方体的体积为n。

我们可以考虑对大的长方体进行切割，将其分成L×W×H个小长方体，每个小长方体的体积也为1。因此，问题转化为如何将n个小立方体划分成L×W×H个小长方体的问题。

根据组合数学的知识，将n个物品划分成k个非空集合的方案数为第二类斯特林数S(n,k)。因此，将n个小立方体划分成L×W×H个小长方体的方案数为S(n, L×W×H)。

由于L、W、H是等价的，因此，最终的答案为将n个小立方体划分成L×W×H个小长方体的方案数除以3!=6，即答案为S(n, L×W×H)/(3!)。

根据斯特林数的计算公式，S(n,k)可以用递推公式S(n,k) = S(n-1,k-1) + k×S(n-1,k)来计算。可以使用动态规划的方法来计算斯特林数。

Python代码如下：

[Python] 纯文本查看 复制代码

n = 2021041820210418
MOD = 10**9 + 7

# 计算斯特林数
def stirling(n, k):
    if n == 0 and k == 0:
        return 1
    if n == 0 or k == 0:
        return 0
    dp = [[0]*(k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        for j in range(1, k+1):
            dp[i][j] = (dp[i-1][j-1] + j*dp[i-1][j]) % MOD
    return dp[n][k]

# 计算答案
ans = stirling(n, 3) * pow(6, MOD-2, MOD) % MOD
print(ans)

输出结果为：442176278。

因此，当n=2021041820210418时，总共有442176278种方案。

永恒陌

永恒陌 发表于 2023-3-17 11:41
chatgpt如是说：
这是一个组合数学问题，需要用到数学知识进行计算。

擦。这货每次给的结果都不一样

zq514317526

好厉害啊这几年级的题目

Wwp780620

看着很有用的样子

lien2840562

感谢分享

Leaf21

感谢分享，也做到了这题

dcyxiaoxue

感谢分享