蓝桥杯上岸每日N题第六期

同步收录

蓝桥杯上岸必背！！！(持续更新中~)

冲刺蓝桥杯省一模板大全来啦 ~

蓝桥杯4月8号就要开始了 ~

距离蓝桥杯省赛倒数第2天

还没背熟模板的伙伴们背起来

真题千千万万遍，蓝桥省一自然现！

日更3000里，蓝桥眷顾你

暴力出奇迹，打表过样例

祝大家4月8号蓝桥杯上岸 ~

不清楚蓝桥杯考什么的点点下方

考点秘籍

蓝桥杯竞赛干货

算法竞赛字符串常用操作总结！！！

往期回顾

蓝桥杯上岸每日N题第一期(一)！！！

蓝桥杯上岸每日N题第一期(二)！！！

蓝桥杯上岸每日N题第一期(三)！！！

蓝桥杯上岸每日N题第二期(一)！！！

蓝桥杯上岸每日N题第三期(一)！！！

蓝桥杯上岸必刷专题

蓝桥杯上岸必刷！！！(日期专题+保姆级教学)

蓝桥杯上岸必刷！！！(字符串专题)

蓝桥杯上岸必刷！！！(模拟/枚举专题)

想背纯享模版的伙伴们点点下方

蓝桥杯省一你一定不能错过的模板大全(第一期)

蓝桥杯省一你一定不能错过的模板大全（第二期）

蓝桥杯省一你一定不能错过的模板大全（第三期）

想背注释模版的伙伴们点点下方

蓝桥杯必背第一期

蓝桥杯必背第二期

蓝桥杯上岸必背！！！ (第三期 DP)

蓝桥杯上岸必背！！！(第四期DFS)

蓝桥杯上岸必背！！！(第五期BFS)

蓝桥杯上岸必背！！！(第六期树与图的遍历)

蓝桥杯上岸必背！！！(第七期最短路算法)

想看JavaB组填空题的伙伴们点点下方

填空题

前言

蓝桥杯后天就要开始啦~还没刷题的同学跟我一起来刷历年真题，迟点出考前鲤鱼锦囊

喜欢的小伙伴可以关注我，关注寸铁，我们一起上岸4.8蓝桥杯！！！

求阶乘

考点：二分+反复整除法

分析

题目问我们的是满足N!的末尾恰好有K个0的最小的N是多少?

思路

阶乘数要想凑出来0必定是有若干个2、5
由于是阶乘2的个数必定是多于5的个数。
因此我们需要去枚举5的个数
没有思路怎么办？

暴力出奇迹，模拟过样例！

10！

10*9*8*7*6*5*4*3*2*1

10、5 总共是2个5
10/5=2

16！

16*15*14*...*10*...*5*...*1

15、10、5总共是3个5
16/5=3
25！

25*...*20*...*15*...*10*...*5

25、20、15、10、5总共有6个5
为什么是6个？
原因在于25可以被拆成5*5，总共是6个5。
所以我们需要反复整除5，这样才能把边界值含5的个数全部统计出来。
最后加上5的个数即可
25/5=5+5/5=6
又如125=5*5*5一共是3个5等于125/5
又如625=5*5*5*5一共是4个5等于625/5

我们通过模拟可以发现：
我们直接对枚举到的数字整除5判断
输出能整除5是k的数字即可

但是看到k的上界为1e18直接枚举必定TLE
题目要求满足N!的末尾恰好有K个0的最小的N
我们需要优化解决,当前N！恰好有k个0。
比N大的N!必定大于K个0,比N小的N！必定小于K个0。

我们直接想到二分来做这道题！！！

怎么二分？

不像最少刷题数那样,满足条件才能进行二分。
这道题直接枚举数字套模板进行二分即可。
因为题目问我们的是最少满足k个0的数字N是多少
不过最后还要检验一下二分出的答案是不是k个0

此外，这题需要考虑一些数据的细节

时间关系,具体看这两个大佬写的博客，写得很棒%%%
博客1
博客2

ACcode

import java.util.*;
public class Main{
    public static void main(String []args) {
        Scanner sc=new Scanner(System.in);
        long k=sc.nextLong();
        long l=1,r=(long)9e18;
        //数据要开大
        //二分
        while(l<r) {

            long mid=l+(r-l)/2;
            //需要再减去l

            //当前的N拆分成5的倍数的个数大于等于k
            //说明需要缩减范围,即r=mid
            if(query(mid)>=k)r=mid;
            //说明不够k需要继续寻找
            else l=mid+1;
        }
        long x=query(r);
        //再查一下N是不是能被拆成k个5
        //可以的话输出r
        //不可以则输出-1
        if(x==k)System.out.println(r);
        else System.out.println("-1");
    }
    static long query(long x) {
        long ans=0;
        //统计能拆分成5的个数
        while(x>0) {
            ans+=x/5;
            //直接让其除以5
            x/=5;
        }
        return ans;
    }
}

提炼

反复整除法：得出某个数的阶乘含a的个数

    static long query(long x) {
        long ans=0;
        //统计能拆分成a的个数
        while(x>0) {
            ans+=x/a;
            //直接让其除以a
            x/=a;
            //再对边界x进行反复整除
            //统计出x还能拆成多少个5/包含多少个5
        }
        return ans;
    }

ACcode2

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner sc=new Scanner(System.in);
        long k=sc.nextLong();
        long l=1;
        long r=(long)9e18;
        while(l<r){
            long mid=l+r>>1;
            if(check(mid)>=k)r=mid;
            else l=mid+1;
        }
        long x=check(r);
        if(x==k)System.out.println(r);
        else System.out.println("-1");
    }
    public static long check(long x){
        long ans=0;
        while(x>0){
          ans+=x/5;
          x/=5;

        }
       return ans; 
    }
}

参考资源

http://t.csdn.cn/2WxI4
https://blog.csdn.net/weixin_57943259/article/details/124206177