计算n!的十进制表示最后有多少个0(南阳ACM_84)

﹏ヽ暗。殇╰゛Y 2021-09-25 21:10 334阅读 0赞

计算公式  
    这里先给出其计算公式，后面给出推导过程。  
    令f(x)表示正整数x末尾所含有的“0”的个数，则有：  
      当0 < n < 5时，f(n!) = 0;

当n >= 5时，f(n!) = k + f(k!), 其中 k = n / 5（取整）。

import java.util.Scanner;
    public class _84 
    {
    	public static void main(String[] args) 
    	{
    		Scanner sc=new Scanner(System.in);
    		int N=sc.nextInt();
    		
    		do
    		{
    			int zz=0;
    			int M=sc.nextInt();
    			if(M<5)
    			{
    				System.out.println(0);
    				continue;
    			}
    			while(M>=5)
    			{
    				M=M/5;
    				zz=M+zz;
    			}
    			System.out.println(zz);
    			N--;
    		}while(N>0);
    		sc.close();
    	}
    
    }
    /*public class _84 {
    	
    	static int f(int M)
    	{
    		if(M==5)
    			return 1;
    		if(M<5)
    			return 0;
    		int m=M/5;
    		return f(m)+m;
    		
    	}
    	public static void main(String[] args) {
    		Scanner sc=new Scanner(System.in);
    		int N=sc.nextInt();
    		int zz;
    		do
    		{
    			int M=sc.nextInt();
    				zz=f(M);
    			System.out.println(zz);
    			N--;
    		}while(N>0);
    		sc.close();
    	}
    
    }
    
    /*
     * http://acm.nyist.net/JudgeOnline/problem.php?pid=84
    
    阶乘的0
    时间限制：3000 ms  |  内存限制：65535 KB
    难度：3
    
    描述
        计算n!的十进制表示最后有多少个0
    
    输入
        第一行输入一个整数N表示测试数据的组数(1<=N<=100)
        每组测试数据占一行，都只有一个整数M(0<=M<=10000000)
    输出
        输出M的阶乘的十进制表示中最后0的个数
        比如5!=120则最后的0的个数为1
    样例输入
    
        6
        3
        60
        100
        1024
        23456
        8735373
    
    样例输出
    
        0
        14
        24
        253
        5861
        2183837
    
    
     */

[计算公式原理：点击打开链接][Link 1]

[Link 1]: http://blog.csdn.net/wjwwgh/article/details/2148270