n的阶乘在m进制下末尾有多少零

 题目来源于CSDN，只是改编为Java版本

推荐看看简单版本：n的阶乘末尾有多少零

代码如下：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    // 寻找的质数的范围，即 [2, maxn]
    static int maxn = 10010;
    // 存所有质数
    static int[] prime;
    static boolean[] isPrime;
    // a存所求数的所有质因子
    static int[] a;
    // b存每个质因子的个数
    static int[] b;
    // num是maxn范围内素数的个数
    static int num, cnt;

    public static void init(){
        a = new int[maxn+1];
        b = new int[maxn+1];
        prime = new int[maxn+1];
        isPrime = new boolean[maxn+1];
        num = 0;cnt = 0;

        // 这里是寻找 maxn 以内的质数
        Arrays.fill(isPrime, true);
        for (int i = 2; i <= maxn; i++) {
            if(isPrime[i]){
                prime[num++] = i;
                for (int j = i*i; j <= maxn; j+=i) {
                    isPrime[j] = false;
                }
            }
        }
    }

    // 找到所有可疑的质数
    private static void decom(int m){
        cnt = 0;
        for (int i = 0; i < num; i++) {
            if(prime[i] > m) break;
            int d = m;
            while (d%prime[i] == 0){
                a[cnt] = prime[i];
                b[cnt]++;
                d /= prime[i];
            }
            if(d < m)
                cnt++;
        }
    }

    // 计算 n! 里面有多少 x，比如8!里面有7个2
    private static long cal(long n, long x){
        if(n == 0 || n == 1){
            return 0;
        }
        long answer = 0;
        while(n != 0){
            answer += n/x;
            n /= x;
        }
        return answer;
    }

    private static long solve(long n, int m){
        decom(m);
        long answer = Long.MAX_VALUE;
        for (int i = 0; i < cnt; i++) {
            long t = cal(n, a[i]);
            answer = Math.min(answer, t/b[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String[] tmp = in.nextLine().split(" ");
            long n = Long.parseLong(tmp[0]);
            int m = Integer.parseInt(tmp[1]);
            init();
            System.out.println(solve(n,m));
        }
    }
}