2021年第12届蓝桥杯 Java B组省赛真题第一场——货物摆放

131 阅读 0 评论 87 点赞

我是靠谱客的博主顺利抽屉，这篇文章主要介绍2021年第12届蓝桥杯 Java B组省赛真题第一场——货物摆放，现在分享给大家，希望可以做个参考。

问题描述】

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
   小蓝有一个超大的仓库，可以摆放很多货物。

    现在，小蓝有 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 位数字）时，总共有多少种方案？

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

【答案提交】

复制代码

1
   这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

阅读完题目你可以清晰的了解到，这道题目的实质考察的就是如何通过 L 、W、H 三个数相乘凑出 2021041820210418

很多小伙伴会直接暴力行事，三个for循环，那我可以明确的告诉你，这在你考试结束之前都跑不出答案，这复杂度太大了，2021041820210418 约等于 2* 10^15 ，三个for那就是执行（2* 10^15）^ 3 =8 * 10^45

这内存都烧“冒烟”了，这固然是行不通的，你也没有那么多的时间去跑！

接下来我将介绍下我的方法，如果对你有帮助，希望点赞评论+关注 ~ . ~

step1 ---首先，我们可以先这个超级大数的所有因子，

step2 ---其次，我们遍历组合这些因子，等于这个超级大数就累计一次

附上代码，如下：

复制代码

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
34
35
36
37
38
39
package test1;
import java.util.*;
import java.math.*;
public class test {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long n=2021041820210418L;
		/* 
		 * 创建因子数组，为什么是128长度，这是因为事先输出了 count = 64，
		 *  然后因为 因子是对称的，且 根号n 无法开整数方根，所以 因子的个数为 2 *count = 128
		 * */
		long[] zhi=new long[128]; 
		int count=0;			
		long i;						
		for(i=1;i*i<n;i++) {
			if(n%i==0) {
				zhi[count]=i; //如果n能整除 i ,则将i装入数组中
				count++; // 求因子个数，并且作为 数组的索引值
			}
		}
		int j=0;
		for(j=64;j<128;j++) {  //求n的另一部分因子，另一部分的因子 = n / 对称因子（比如63和64是对称的，62和65是对称的）
			zhi[j]=n/zhi[127-j];
		}
		
		int s=0;    //开始遍历因子数组，如果相乘等于 n ，则计数器计数一次
		for(int x=0;x<128;x++) {		
			for(int p=0;p<128;p++) {			
				if(zhi[x]*zhi[p]>n) break; // 减少一定的 “余坠”，大于n直接跳出，减少复杂度和运算时间
				for(int q=0;q<128;q++) {
					if(zhi[x]*zhi[p]*zhi[q]==n) {
						s++;
					}
				}
			}
		}
		System.out.println(s);
	}
}