题目描述
求 n ! n! n! 中某个数码出现的次数。
输入格式
第一行为 t ( t ≤ 10 ) t(t \leq 10) t(t≤10),表示数据组数。接下来 t t t 行,每行一个正整数 n ( n ≤ 1000 ) n(n \leq 1000) n(n≤1000) 和数码 a a a。
输出格式
对于每组数据,输出一个整数,表示 n ! n! n! 中 a a a 出现的次数。
样例 #1
样例输入 #1
2
5 2
7 0
样例输出 #1
1
2
1.题目分析
输入一个t代表数据的组数,每组数据有两个数,计算第一个数的阶乘,统计阶乘结果中第二个数的出现次数并打印。
乍一看,这道题用递归和函数就能轻松解决,但是计算阶乘的输入可以是1000的,所以又涉及到了高精度的乘法。
本人愚钝之前用c++写过A*B的高精度乘法,代码很长,这道题偷点懒就是用Java的高精度来计算会方便很多。
当然用c++也是可以写的,用整型数组存储阶乘结果的每一位数字,或者用字符数组存储结果都可以。
使用Java计算高精度之前,我们要了解Java中BigInteger的用法,我在之前的博客中有所提及: BigInteger的用法
2.题目思路
编写一个递归函数:
用于计算一个数的阶乘,设置递归出口为,当n==1时,返回1,
其他情况n连乘递减的函数即可。文章来源:https://www.toymoban.com/news/detail-674192.html
输入 t,循环t次,每一次输入一个正整数和数码,调用递归函数得到阶乘,
再用while循环得到阶乘结果的每一个数字,与数码进行比较并计数。
每循环一轮打印一次计数结果即可。文章来源地址https://www.toymoban.com/news/detail-674192.html
3.代码实现
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
//新建输入函数
Scanner sc = new Scanner(System.in);
int n, a, t;
//计数器
int cnt;
//输入数据组数
t = sc.nextInt();
for (int i = 0; i < t; ++i) {
//每一轮计数器归零
cnt = 0;
//输入正整数和数码
n = sc.nextInt();
a = sc.nextInt();
//调用得到阶乘结果
BigInteger res = factorial(BigInteger.valueOf(n));
//计算每一位中a出现的个数
//循环条件等价于 res != 0
while (!res.equals(BigInteger.valueOf(0))) {
//等价于 res % 10 == a
//这里是调用了除法函数,返回的是数组:商和余数,所以索引是1
if (res.divideAndRemainder(BigInteger.valueOf(10))[1].equals(BigInteger.valueOf(a))) {
cnt++;
}
//等价于 res = res / 10
res = res.divide(BigInteger.valueOf(10));
}
//打印每一轮的结果
System.out.println(cnt);
}
}
//阶乘函数
public static BigInteger factorial(BigInteger n) {
//等价于 n == 1
if (n.equals(BigInteger.valueOf(1))) {
//等价于 return 1;
return BigInteger.valueOf(1);
}
//等价于 n * factorial(n - 1)
return n.multiply(factorial(n.subtract(BigInteger.valueOf(1))));
}
}
到了这里,关于P1591 阶乘数码(Java高精度)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!