蓝桥杯准备——BigIntenger（大数类型）以力扣每日一题“ 阶乘后的零”为例
今天准备蓝桥杯的时候遇到了一道大数类型的题目，尝试，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=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进制为例子：
//进制转换@Testpublic void testScale() {//在构造将函数时，把radix进制的字符串转化为BigIntegerString str = "1011100111";int radix = 2;BigInteger interNum1 = new BigInteger(str,radix);//743//我们通常不写，则是默认成10进制转换，如下：BigInteger interNum2 = new BigInteger(str);//1011100111}当然BigInteger也可以由键盘读入：
//读入方法：nextBigInteger()@Testpublic 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=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; }}测试一下：果然：
果然是大佬！！！我这个菜鸡实锤！！！蓝桥杯不参加也罢！！！
