货物摆放
本文最后更新于 207 天前,其中的信息可能已经有所发展或是发生改变。

货物摆放

小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 LWH 的货物,满足 n=L×W×H

给定 n,请问有多少种堆放货物的方案满足要求。

例如,当 4时,有以下 6 种方案:1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×11×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。

请问,当 n=2021041820210418 (注意有 16 位数字)时,总共有多少种方案?

**解法一(用到ArrayList集合)

这一种解法是刷题网站的一位高手写的,他的思路写的很清晰!

我当时做这题的时候,也是用的暴力算法,但是时间复杂度太高了,以至于我没有在规定时间内得出答案,也没有得出答案,

数据通过率0%

 import java.util.ArrayList;
 
 public class Main {
     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<>();
 
         //从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);
 
    }
 }

解法二:c++纯算法(暴力相应的减少了循环次数)

 #include <iostream>
 using namespace std;
 int main()
 {long long n=2021041820210418;
     long long k,s,sum=0;
     for(long long i=1;i*i*i<=n;i++){
         if(n%i==0){
             s=n/i;
             for(long long j=i;i*j*j<=n;j++){
                 if(s%j==0){
                     k=n/i/j;
                     if(i==j&&i==k)
                         sum++;
                     else if(i==j&&i!=k)
                         sum+=3;
                     else  
                         sum+=6;
                }
            }
        }
    }
     printf("%d",sum);
   // 请在此输入您的代码
   return 0;
 }
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇