阶乘计算(JAVA)

题目描述

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

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

输入格式

一个整数 K。

输出格式

一个整数代表答案。

样例输入

样例输出

提示

对于 30% 的数据，1 ≤ K ≤ 106 .

对于 100% 的数据，1 ≤ K ≤ 1018

代码1：暴力解法

利用取余，遍历1~10^18（题目中100%的数据规模）内所有数，对每个数取余判断是否为K个0，很明显是超时了。但可以得到部分的分数，没有时间的话可以这样简单处理。

public class Lanqiao2674 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
        int n=1;
        for (int i = 0; i < k; i++) {
            n*=10;
        }
        long sum=1;
        int flag=0;
        for (int i = 1; i<1000000; i++) {
            sum*=i;
            if(sum%n==0){
                flag=1;
                System.out.println(i);
                break;
            }
        }
        if(flag==0){
            System.out.println(-1);
        }
    }
}

点击并拖拽以移动

代码分析：这个是计算末尾0的个数的代码，很明显在这个环节就没办法达到100%数据的要求，因为1≤K≤10^18，而这个代码复杂度是O(n),要计算10^18次，但蓝桥杯计算量一般不超过10^8，所以用暴力法计算是超时的。

代码2：二分法求解

直接算出k个0的N!很难。N! 末尾的 0 取决于1 到 N 各因子2 和 5 的组合个数，但是实际上5的个数小于2的个数，所以末尾0的个数实际取决于 5 的个数。

结论：求N的阶乘中因子5的个数,将N每次除以5的商****求和即可。

由此可编写一个统计0的个数的方法为：

public static long zero(long n){
        long res=0;
        while(n!=0){
            res+=n/5;
            n/=5;
        }
        return res;
    }

点击并拖拽以移动

public class Lanqiao2674new{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        //输入的数字应为long。原因是阶乘算出的结果较大，用int会溢出。
        long k=sc.nextLong();

        //利用二分查找，找到符合0个数的最小数字
        long left=0,right=Long.MAX_VALUE;
        while(left<right){
            long mid=left+(right-left)/2;
            if(zero(mid)<k)left=mid+1;
            else right=mid;
        }

        //此时left就是我们求出的结果
        long res=zero(left);//可能不为k。
        if(res==k)System.out.println(left);//若和k相等，则是找到了数字left的阶乘结果又k个0。
        else System.out.println(-1);//不相等则返回-1;
        sc.close();
    }

    //统计0的个数的函数
    public static long zero(long n){
        long res=0;
        while(n!=0){
            res+=n/5;
            n/=5;
        }
        return res;
    }
}