准备蓝桥杯比赛的过程中，刷的一些真题和部分算法的学习

/*题目： 货物摆放 * 例如：当n==4时：有以下 66 种方案： * 1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1 * 请问，当 n = 2021041820210418n=2021041820210418 （注意有 1616 位数字）时，总共有多少种方案？ * */ /*核心思想： * 1.三个数的乘积要想等于num的话，那么这三个数肯定都是numd的因子（能够被num整除） * 2.找出num的所有因子存放到ArrayList中 * 3.找num的所有因子的技巧：先找到一个小因子，通过这个小因子，找到这个小因子对应的大因子 * 4.注意：Math.sqrt(num)会重复一个 * 5.三重循环遍历ArrayList，得到结果 * */ package Test; import java.util.ArrayList; public class C113 { public static void main(String args[]) { //常规思路 /* long num = 2021041820210418l; int count = 0; for ( long i = 1 ; i < num ; i++ ){ for ( long j = 1 ; j < num ; j++ ){ for ( long k = 1 ; k < num ; k++ ){ if ( i * j *um ){ count++; } } } } */ //显而易见，这个算法的时间复杂的非常的大。计算机想要算出结果，可能需要几天的时间 //所以要另辟蹊径 //想想，三个数相乘要等于num，那么这三个数是不是都是num的因子，都能被num整除呢？ //上方的算法，三层for循环都是从1遍历到num，其中很多组合都是无效的 //简而言之，这些无效组合中的数不能同时被num整除，而有效的组合，任何一个数都能被num整除 //所以，如果我们能从num的因子里面去找组合，是不是时间复杂度就要小许多？ long num = 2021041820210418l; //如果直接赋值,计算机默认数字是int类型，会报错。所以要在后面加'l'，转换为long类型 //定义一个ArrayList数组，存放num的因子 ArrayList<Long> arr = new ArrayList<>(); //将num的因子存放到ArrayList数组中 //从1开始遍历，遍历到num的平方根结束。不需要把num遍历一遍，这样算法复杂都也非常大，重点看for循环里面的语句 for ( long i = 1 ; i <= Math.sqrt(num) ; i++ ){ //每一次循环都是先得到较小的因子，然后通过较小的因子得到较大的因子 if ( num % i == 0 ){ arr.add(i); //如果能被整除，就放到arr数组中-----放的是较小的因子 //！！！重点在这里，当i能被num整除的情况下，求出num关于i的另外一个除数n //这样，for循环不需要从1遍历到num。可以通过较小的因子，求出另外一个较大的因子 long n = num / i; //如果num = Math.sqrt(num)*Math.sqrt(num),那么由较小的因子求较大的因子时，会重复，要排除这种情况 if ( n != i ){ //当然，此时num，不会出现这种情况。如果num=4，就会出现这种情况 arr.add(n); //将较大的因子放入arr数组 } } } //System.out.println(arr.size()); //num一共有128个因子 //三层for循环依次遍历即可。 128^3 = 2097152 计算机完全可以在短时间内算出结果 int count = 0; for ( long i : arr ){ for ( long j : arr ){ for ( long k : arr ){ if ( i * j * k == num ){ count++; } } } } System.out.println(count); } }