P1591 阶乘数码(Java高精度)

题目描述

求 $n!$ 中某个数码出现的次数。

输入格式

第一行为 $t(t\le 10)$，表示数据组数。接下来 $t$ 行，每行一个正整数 $n(n\le 1000)$ 和数码 $a$。

输出格式

对于每组数据，输出一个整数，表示 $n!$ 中 $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连乘递减的函数即可。

输入 t，循环t次，每一次输入一个正整数和数码，调用递归函数得到阶乘，
再用while循环得到阶乘结果的每一个数字，与数码进行比较并计数。
每循环一轮打印一次计数结果即可。

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 != 0while (!res.equals(BigInteger.valueOf(0))) {//等价于 res % 10 == a//这里是调用了除法函数，返回的是数组：商和余数，所以索引是1if (res.divideAndRemainder(BigInteger.valueOf(10))[1].equals(BigInteger.valueOf(a))) {cnt++;}//等价于 res = res / 10res = res.divide(BigInteger.valueOf(10));}//打印每一轮的结果System.out.println(cnt);}}//阶乘函数public static BigInteger factorial(BigInteger n) {//等价于 n == 1if (n.equals(BigInteger.valueOf(1))) {//等价于 return 1;return BigInteger.valueOf(1);}//等价于 n * factorial(n - 1)return n.multiply(factorial(n.subtract(BigInteger.valueOf(1))));}
}