蓝桥杯2021年省赛java B组第四题

题目

小蓝有一个超大的仓库,可以摆放很多货物。现在,小蓝有 箱货物要摆放在仓库,每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向,每箱货物的边都必须严格平行于长.宽、高。小蓝希望所有的货物最终摆成一个大的长方体。

即在长、宽、高的方向上分别堆 L、W、H 的货物,满足n=Lx WXH。
给定 n,请问有多少种堆放货物的方案满足要求。
例如,当n=4 时,有以下6种方案: 1x1x4、1x2x2、1x4x1、2x1x2、2x2x1、4x1x1.
请问,当 n =2021041820210418 (注意有 16 位数字) 时,总共有多少种方案?
提示:建议使用计算机编程解决问题。

答案

思路

这个思路看起来很简单,其实也就是找出这个数的所有因子然后再因子里随机找出3个数相乘得到这个数

那么就有一个经典的问题,如何快速找出一个大数的所有因子

最简单的暴力方法是一个一个%,然后输出,可想而知,很慢,尤其是这个数(2021041820210418)很大

    public static void getFactorViolence(long num){//得到所有因子
        for (long i = 1; i <= num; i++) {
            if (num % i == 0) {
                System.out.println(i);
            }
        }
    }

那么可以稍微优化一下,这个可以用一个相对较小的数来理解

比如100,100的因子有[1, 2, 4, 5, 10, 20, 25, 50, 100]

从1开始,直到开平方前的每一个因子,在比开平方大的后面一定有一个对应的因子,直达开平方

1对应100

2对应50

4对应25

5对应20

10对应10

那么就需要一个不可以存在相同值的Set集合来承接

    public static Set<Long> getFactor(long num){//得到所有因子
        Set<Long> ans = new HashSet<>();//可以理解为链表,但不能存在重复值
        long end = (long)Math.sqrt(num);//开平方
        for (long i = 1; i <= end; i++) {
            System.out.println((double) i/end * 100+"%");//进度
            if (num % i == 0) {
                ans.add(num/i);//找对应值
                ans.add(i);
            }
        }
        return ans;
    }

即使是这样,由于这个数实在是太大,跑完全部也需要至少两分钟,所有加一个进度是很有必要的,不然看着空白的一片很容易怀疑陷入了死循环

接下来就是将set放回数组内

        Set<Long> ans = getFactor(2021041820210418L);
        System.out.println(ans.size());
        Long[] arr = ans.toArray(new Long[0]);//注意是Long类
        Arrays.sort(arr);//无需排序,排序只是为了好看
        System.out.println(Arrays.toString(arr));

接下来就是循环找组合,只有128个数,纯暴力也很快

int size=0;        
for (long i : arr) {
    for (long j : arr) {
       for (long k : arr) {
           if (i * j * k == 2021041820210418L) {
               size++;
           }
       }
    }
}
System.out.println(size);

完整代码

package blue.T2021_4;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<Long> ans = getFactor(2021041820210418L);//得到所有因子
        System.out.println(ans.size());//因子数量,实际上没必要
        Long[] arr = ans.toArray(new Long[0]);//放入Long[]数组,是Long类
        Arrays.sort(arr);//排序,只是为了好看
        int size = 0;//初始化size
        System.out.println(Arrays.toString(arr));//打印数组
        for (long i : arr) {
            for (long j : arr) {
                for (long k : arr) {//暴力循环
                    if (i * j * k == 2021041820210418L) {//判断
                        size++;
                    }
                }
            }
        }
        System.out.println(size);
    }

    public static Set<Long> getFactor(long num) {//得到所有因子
        Set<Long> ans = new HashSet<>();
        long end = (long) Math.sqrt(num);
        for (long i = 1; i <= end; i++) {//因子最大值是该数的开平方
            System.out.println((double) i / end * 100 + "%");
            if (num % i == 0) {
                ans.add(num / i);
                ans.add(i);
            }
        }
        return ans;
    }

    static Long[] fator = {1L, 2L, 3L, 6L, 9L, 17L, 18L, 27L, 34L, 51L, 54L, 102L, 131L, 153L, 262L, 306L, 393L, 459L, 786L, 918L, 1179L, 2227L, 2358L, 2857L, 3537L, 4454L, 5714L, 6681L, 7074L, 8571L, 13362L, 17142L, 20043L, 25713L, 40086L, 48569L, 51426L, 60129L, 77139L, 97138L, 120258L, 145707L, 154278L, 291414L, 374267L, 437121L, 748534L, 874242L, 1122801L, 1311363L, 2245602L, 2622726L, 3368403L, 5882353L, 6362539L, 6736806L, 10105209L, 11764706L, 12725078L, 17647059L, 19087617L, 20210418L, 35294118L, 38175234L, 52941177L, 57262851L, 100000001L, 105882354L, 114525702L, 158823531L, 171788553L, 200000002L, 300000003L, 317647062L, 343577106L, 600000006L, 770588243L, 900000009L, 1541176486L, 1800000018L, 2311764729L, 2700000027L, 4623529458L, 5400000054L, 6935294187L, 13100000131L, 13870588374L, 16805882521L, 20805882561L, 26200000262L, 33611765042L, 39300000393L, 41611765122L, 50417647563L, 78600000786L, 100835295126L, 117900001179L, 151252942689L, 235800002358L, 285700002857L, 302505885378L, 353700003537L, 453758828067L, 571400005714L, 707400007074L, 857100008571L, 907517656134L, 1714200017142L, 2201570610251L, 2571300025713L, 4403141220502L, 5142600051426L, 6604711830753L, 7713900077139L, 13209423661506L, 15427800154278L, 19814135492259L, 37426700374267L, 39628270984518L, 59442406476777L, 74853400748534L, 112280101122801L, 118884812953554L, 224560202245602L, 336840303368403L, 673680606736806L, 1010520910105209L, 2021041820210418L};
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


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