蓝桥杯2022年省赛JAVA B组第五题

题目

满足 N!的末尾恰好有 K个 0的最小的 N是多少?

如果这样的 N,不存在输出 −1

输入格式

一个整数 K

输出格式

一个整数代表答案。

数据范围

对于 30%的数据,1≤K≤106
对于 100%的数据,1≤K≤1018

测试地址:官方测试地址

思路

对于末尾有多少0,这个问题可以转化为在阶乘的所有相乘的项内,能转化出多少10,比如

5! = 5 * 4 * 3 * 2 * 1 = ( 2 * 5 )* 3 * 1 * 4 = 10 * 3 * 4 * 1 = 120.

10! = 10 * 9 * 8 * 7 * 6 * 5 * 5 * 4 * 3 * 2 * 1 = 10 * 5 * 2 * …… = 3628800

我们接着可以得到阶乘各项中10的个数与5密切相关,因为偶数的数目一定比5多,任何一个5的幂次倍都可以乘以一个指定的偶数变为10的幂次倍。

简单来说就是

5 * 2 = 10 = 101

25 * 4 = 100 = 102

125 * 8 = 1000 = 103

那非5的幂次倍的,但是它是5的倍数可不可以分出10来呢?,比如15 = 5 *3 ,只需要再来一个任意的偶数分出的2就可以分出一个10。

那么现在就知道是0的个数就是阶乘中每一项能分出的5的个数。

这个个数该如何计算呢?

你现在已知的是有最后有几个0,也就是阶乘各项分解之后有几个5.

5101520253035125175200625
可分出的5的个数11112113224

通过上表可以看出5的幂次倍可以分出相应次数个5,而5 的倍数能分出的5的个数就取决于它是单是5 的倍数还是也是5的幂次方的倍数。

但我们应该如何去计算这个5的个数呢?

我们可以看出,10 – 25一共可以提取出5个5,这个5正好是25/5

30 – 125 一共可以提取25个5(可以看这个Excel表),这个正好也是125/5 = 25

那么对于5的总数就可以All = N / 5 + N / 25 + N / 125 + N / 5i

对于这样的话,我们可以根据给出的数据范围去判断一下最大的5i是多少,并将它放到一个long的数组内,对于这个我们最好是数组准备的大一些,但是1e19甚至会超过long的最大值,所以可以用2e18。

    public static void get(){
        System.out.print("{");
        long i=5;
        while (i<2e18){
            System.out.print(i+"L,");
            i*=5;
        }
        System.out.print("}");
    }

得到以下数组

    long[] arr = {5L,25L,125L,625L,3125L,15625L,78125L,390625L,
            1953125L,9765625L,48828125L,244140625L,1220703125L,
            6103515625L,30517578125L,152587890625L,762939453125L,
            3814697265625L,19073486328125L,95367431640625L, 
            476837158203125L, 2384185791015625L,11920928955078125L,
            59604644775390625L,298023223876953125L,1490116119384765625L};

那么对于任何一个数都可以计算出可以提取出多少5,也就可以判断末尾有多少0

    public static long getZero(int n){
        long ans = 0L;
        for (long l : arr) {//arr就是上面的arr,为了这里使用,需要将arr定义为类变量,并且静态
            ans += n / l;
        }
        return ans;
    }

这里其实在本地就可以暴力去循环得到指定的答案

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long k = scanner.nextLong();
        long i = 5;
        while (true){
            long num = getZero(i);
            if (num == k) {
                System.out.println(i);
                break;
            }else if (num<k){
                i++;
            }else {
                System.out.println(-1);
                break;
            }
        }
    }

很好理解从5开始是末尾一个0,之后依次每个判断,直到得到正确结果或者以已经超过指定的K就可以break,这样的复杂度看似也只有O(N)但是要注意的是,这个N太大了,数据范围K要达到10的18次方。

因此我们可以用一下二分查找

二分查找

既然要二分那么就需要一个范围,左边界一定就是5,那么这个最大值应该是多少呢?

最大的应该是要阶乘的结果比末尾10的18次方颗0大的多的那个数,但是说实在的,谁也不知道那是个啥数,所以索性就先使用long的最大值

long L = 5L;
long R = Long.MAX_VALUE;

然后就是很平常的二分过程

二分的标志是该数的getZero()

如果少于要求的k值,那么这个数还不够大,就只要左半部分。也就是将有边界设置为mid

如果大于k值,那么这个数还不够小,要将左边界设为mid+1

while (L < R){
    long mid = (L+R)/2;
    if (getZero(mid) < k){
        L = mid+1;
    }else {
        R = mid;
    }
}

查找到最后的结束就是一个L=R。

这个就是最后的可能结果

这时需要再进行一次判断

if (getZero(R) == k){
    System.out.println(R);
}else {
    System.out.println(-1);
}

那么这就是全部的思路了。

但是这个最大的右值依然有问题

假如我们去提交

该图为AcWing测试截图,地址为AcWing1666求阶乘

假如我们输入指定的数据范围的最大值1018,我们会发现很久都没有结果,那么我们就可以自己去减小范围,可以用下面这个来计算一下时间

long start =System.currentTimeMillis();
…………
…………
long end = System.currentTimeMillis();
System.out.println(end-start);

减小范围可以先直接用这个最大值减一个数去尝试

在最大值减去5的时候就出现了1ms出结果的情况,虽然不清楚是啥情况,但是现在就可以100%通过测试

蓝桥杯官方测试地址

完整代码

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static long[] arr = {5L,25L,125L,625L,3125L,15625L,78125L,390625L,
           1953125L,9765625L,48828125L,244140625L,1220703125L,
            6103515625L,30517578125L,152587890625L,762939453125L,
            3814697265625L,19073486328125L,95367431640625L,
            476837158203125L, 2384185791015625L,11920928955078125L,
            59604644775390625L,298023223876953125L, 1490116119384765625L};
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //long start =System.currentTimeMillis();
        long k = scanner.nextLong();
        long L = 5L;
        long R = Long.MAX_VALUE-5;
        while (L < R){
            long mid = (L+R)/2;
            if (getZero(mid) < k){
                L = mid+1;
            }else {
                R = mid;
            }
        }
        if (getZero(R) == k){
            System.out.println(R);
        }else {
            System.out.println(-1);
        }
        //long end = System.currentTimeMillis();
        //System.out.println(end-start);
    }
    public static void get(){
        System.out.print("{");
        long i=5;
        while (i< 2e18){
            System.out.print(i+"L,");
            i*=5;
        }
        System.out.print("}");
    }

    public static long getZero(long n){
        long ans = 0L;
        for (long l : arr) {
            ans += n / l;
        }
        return ans;
    }
}
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


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