货物摆放 (蓝桥杯) JAVA

题目描述

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

提示：建议使用计算机编程解决问题。

解题思路：由于 n 数据的庞大，可以用 long 来储存，如果直接用三重 for 循环来解题的话，大概需要 2h左右。

所以纯暴力破解是不讨好的，需要在此基础上添加一点点技巧。

由例题可看出：n = 4 的时候，L, W, H内出现的都是 n 的约数，即都能被 n 整除。所以我们不妨先寻找 n 的约数，再暴力破解。

1.寻找 n 的约数的代码如下：

 for(long i = 1; i*i <= n;i ++) {
    	  if(n % i == 0) {
    		  s.add(i);
    		  if(n / i != i) s.add(n / i);
    	  }
      }

即：我们在1 ~ n^(1/2) 这个区间内寻找约数，由于有s.add(n / i) 的存在后半部分的约数也一起存储了（例如 6 % 2 == 0，存入 2，6 / 2 = 3，也一起存入），我们没必要查找后半部分（如果查找则会重复）。

上述查找约数的部分大概需要循环 10^8 左右，计算机 1 s 左右就能办完。

2.需要用一个容器储存这些约数，我用的是 list 容器，这个还是比较好用的。

3.由于算式不能重复，我们直接利用三重for循环筛选符合体条件的约数即可，由于约数不是太多，三重for循环也用不了几秒时间。

理论成立完整代码如下：

import java.util.ArrayList;
import java.util.List;

public class Main {
	 
	public static void main(String[] args){
       long n = 2021041820210418L;
       List s = new ArrayList<Long>();
       for(long i = 1; i * i <= n; i ++) {
    	   if(n % i == 0) {
    		   s.add(i);
    		   if(n / i != i) s.add(n / i);
    	   }
       }
       int sum  = 0;
       for(int i = 0; i < s.size(); i ++)
    	   for(int j = 0; j < s.size(); j ++)
    		   for(int k = 0; k < s.size(); k ++) 
    			   if((long)s.get(i) * (long) s.get(j) * (long) s.get(k) == n) sum ++;
       System.out.print(sum);
    }
}