-->

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));
}
}
}

特别说明

由于众所周知的原因,本博客以往文章的图片无法显示,请谅解。

标签

生活纪实 (191) 感想 (115) ingress (54) 软件 (49) 小诗 (35) 梦境 (28) 教程 (21) 科幻 (21) 体会 (20) 杭州 (11) blogger (5) wordpress (5) Google adsense (4) Google voice (3) Chrome (2) Tensorflow (1) 谷粉 (1)