蓝桥杯准备——BigIntenger（大数类型）以力扣每日一题“ 阶乘后的零”为例_蓝桥杯可以用biginteger

今天准备蓝桥杯的时候遇到了一道大数类型的题目，尝试，int和long均不行后才发现这是一道大数类型题目。题目如下：

给定一个整数 n ，返回 n! 结果中尾随零的数量。
 
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
 
示例 1：
 
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
 
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
 
输入：n = 0
输出：0
提示：
 
0 <= n <= 104
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？

我的尝试：思路：不就是解决阶乘后的零问题吗，从几开始阶乘以及告诉我了，就是n，那还不简单，直接从n乘到1，然后用一个循环倒着遍历就行了吗，遇到0就加一，遇到第一个不是0的就跳出循环不就完了吗，于是写下的如下代码：

package test;
 
import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner  scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		long sum=1;
		
		for(int i=0;i<n;i++) {
			sum=sum*(n-i);
		}
		int sum1=0;
		String string=Long.toString(sum);
		String[] s = string.split(""); 
		for(int i=s.length-1;i>=0;i--) {
			if(s[i].equals("0")) {
				sum1++;
			}else {
				break;
			}
		}
		if(n==0) {
			sum1=0;
		}
		else {
			
		}
		System.out.print(sum1);
	}
 
}

于是就很愉快的只通过了测试数据中的21/50,

 我一看测试数据：30？30的阶乘，那不是大数了吗，这才反应过来要用大数来做。（之前尝试过long类型也不行）（int最多表示 2^31-1）

BigInteger类型的数字范围较Integer，Long类型的数字范围要大得多，它支持任意精度的整数，也就是说在运算中 BigInteger 类型可以准确地表示任何大小的整数值而不会丢失任何信息。

更多关于Intenger的信息可以参考这篇博客：Java中BigInteger类的使用方法详解，常用最全系列！_Java Punk的博客-CSDN博客_biginteger用法

 其实，BigInteger的构造方法与String非常相似，只是大数类型的定义需要在括号里写上Str还有可能写上数据的类型，支持各种进制。如下以2进制为例子：

	//进制转换
	@Test
	public void testScale() {
		//在构造将函数时，把radix进制的字符串转化为BigInteger
		String str = "1011100111";
		int radix = 2;
		BigInteger interNum1 = new BigInteger(str,radix);	//743
 
		//我们通常不写，则是默认成10进制转换，如下：
		BigInteger interNum2 = new BigInteger(str);			//1011100111
	}

当然BigInteger也可以由键盘读入：

	//读入方法：nextBigInteger()
	@Test
	public void test5() {
		Scanner scan = new Scanner(System.in);				// 读入
		int n = scan.nextInt(); 							// 读入一个int;
		BigInteger m = scan.nextBigInteger();				// 读入一个BigInteger;
		while(scan.hasNext()){	
			System.out.print("scan.hasNext()=" + scan.hasNext());
		}
	}

到这里我们就可以解决问题了吗？不行，原因是我们虽然知道了怎么构造大数类型，但是我的大数产生的途径是不断成出来的，怎么由整数类型成出大数类型呢？

有办法，而且说出来你可能要笑：把原来的整数全部定义为大数不就行了吗？哈哈哈哈哈！！！

如下：我们先需要把原有的String类型的数，再将其变为BigInteger类型。

package test;
 
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
	public static void main (String[] args) {
		Scanner  scanner = new Scanner(System.in);
		int n=scanner.nextInt();
		BigInteger sum=new BigInteger("1");
		
		for(int i=0;i<n;i++) {
			String temp=Integer.toString(n-i);
			BigInteger big = new BigInteger(temp);
			sum=sum.multiply(big);
		}
		int sum1=0;
		String string=sum.toString();
		String[] s = string.split(""); 
		for(int i=s.length-1;i>=0;i--) {
			if(s[i].equals("0")) {
				sum1++;
			}else {
				break;
			}
		}
		if(n==0) {
			sum1=0;
		}
		else {
			
		}
		System.out.print(sum1);
	}
 
}

我们以为大功告成了，然而.......

我们却得到了：

 神马？7268，你逗我呢，不就50个测试用例吗，不1-50就行了吗，这也太过分了吧，大的有点离谱了吧！！！

于是我又开始了我漫长的思考，确实，如果要算7268的阶乘，大数也难做到啊，但是我们不是只需要阶乘最后的0的个数吗，是不是根本不用暴力的把阶乘真正的求出来，而只需要看最后的0有几个就好了呢？

实在想不出来了，我就去看了官方题解：

当时进入这个官方题解就给我一种不好的预感，因为我看见了“不祥之兆”的标签：

 脑筋急转弯！！！md

结果不出我所料：官方题解中连一个大数；类型的影子都没看见，甚至只用了5行代码就解决了这个问题：数学方法+脑经急转弯！！！

思路如下：

n! 尾零的数量即为 n!n! 中因子 1010 的个数，而 10=2\times 510=2×5，因此转换成求 n!n! 中质因子 22 的个数和质因子 55 的个数的较小值。
 
由于质因子 55 的个数不会大于质因子 22 的个数（具体证明见方法二），我们可以仅考虑质因子 55 的个数。
 
而 n!n! 中质因子 55 的个数等于 [1,n][1,n] 的每个数的质因子 55 的个数之和，我们可以通过遍历 [1,n][1,n] 的所有 55 的倍数求出。

代码如下：

class Solution {
    public int trailingZeroes(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            for (int x = i; x % 5 == 0; x /= 5) {
                ++ans;
            }
        }
        return ans;
    }
}

测试一下：果然：

 果然是大佬！！！我这个菜鸡实锤！！！蓝桥杯不参加也罢！！！