n!末尾0的个数之计算

文通过数学分析给出了输出n!末尾0的个数之函数的递归形式,并同时给出了两种本问题的枚举解法。

问题描述

给定正整数n, 计算n!末尾0的个数。例:

5! = 120, 故 5! 结尾0的个数为1.
10! = 3628800, 故 10! 结尾0的个数为2.
25! = 15511210043330985984000000, 故 25! 结尾0的个数为6.

分析

导致末尾0出现的原因

众所周知,当一个正整数n与10相乘时会产生进位,即10n的末尾会比n多1个0。类似地,当一个正整数n与\(10^{k}\)相乘时,所得结果的末尾会比n多k个0. 又,由算术基本定理:

每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

可知欲计算n!末尾0的个数,只需查找其分解中10的个数,也即查找n!的素因子分解中相乘等于10的两个质数组合的个数。

命题1:10的素因子分解是2 * 5.

证明:因为10是合数,所以10可记作多个质数之积。又因为10是偶数,所以10的素因子分解不能全为奇数。而偶素数只有2,故10的素因子分解中必有2,又10 / 2 = 5, 故10的素因子分解为2 * 5. 证毕。

由此可见,欲计算n!末尾0的个数,只需统计n!的素因子分解中因子(2 * 5)的个数。又,因为奇数与偶数交替出现,所以每2个连续数字就会出现一个因子2,而每5个连续数字才会出现一个因子5,故因子(2 * 5)的个数即因子5的个数。此时,原问题转化为:计算n!的素因子分解中5的个数。

计算n!的素因子分解中5的个数

为了计算正整数n的素因子分解中5的个数,我们可以计算n的某个分解中5的倍数的个数。

由除法定理,任一正整数\(n\)可记作\(n=5k+r\), 其中\(k=\left \lfloor \frac{n}{5} \right \rfloor\), \(0\leq r\leq 4\)。则\(n!\)的一个分解为$$n!=5k \cdot 5(k - 1) \cdot 5(k - 2) \cdots 5 \cdot A $$,即$$ n!=5^{k} \cdot k! \cdot A$$,其中\(A\)为不含因子5的因子。

此时定义函数\(f(n)\)输出正整数\(n\)末尾0的个数,\(g(n)\)输出正整数\(n\)素因子分解中因子5的个数。由前述易知\(f(n) = g(n)\). 此时由g(n)的性质可导出以下命题:

命题2:\(g(\prod_{i = 1}^{k} a_{i}) = \sum_{i = 1}^{k} g(a_{i})\), \(a_{i}\in \mathbb{Z}\)且\(a_{i}\neq 0\).

证明:\(\prod_{i = 1}^{k} a_{i}\)的素因子分解为\(a_{1}, a_{2}, \cdots, a_{u}, \cdots, a_{i}\)的素因子分解之积,而后者中因子5出现的次数为数列\(a_{i}\)中每个元素之素因子分解中因子5出现的次数之和,故知前者的素因子分解中因子5的个数也等于上述和。证毕。

故知\(f(n) = g(n) = g(5^{k} \cdot k! \cdot A) = k + g(k!) = k + f(k!)\), 其中\(k = \left \lfloor n / 5 \right \rfloor\). 又易知\(f(n!) = 0\ (0 \leq n \leq 4)\), 此时即获得\(f(n!)\)的递归关系,这就是所求问题的解。例:

f(5!) = 1 + f(1!) = 1
f(10!) = 2 + f(2!) = 2
f(25!) = 5 + f(5!) = 5 + 1 + f(1!) = 6

代码实现

int FactZero(int n){
    return n <= 4 ? 0 : (n / 5) + FactZero(n / 5);
}

枚举法

如果直接试图编程计算该问题,很容易导致溢出。但在进行了以上分析之后,即使未能得出最后的递归关系,只要知道求解本题只需统计n的素因子分解中5出现的次数,此问题亦可以用枚举法求解。

统计5的倍数(5,10,15,20,25(= 5 ^ 2))出现次数

int FactZero(int n){
    if(n <= 4)
        return 0;
    else{
        int i = 0, j = 0, count = 0;

        for(i = 5; i <= n; i += 5){
            j = i;
            while(j % 5 == 0){
                count++;
                j /= 5;
            }
        }
        return count;
    }
}

递归关系式的迭代形式

由上文分析的递归关系式,可知$$f(n!) = \left \lfloor n / 5 \right \rfloor + f(\left \lfloor n / 5 \right \rfloor!)$$$$=\left \lfloor n / 5 \right \rfloor + \left \lfloor n / 5^{2} \right \rfloor + f(\left \lfloor n / 5^{2} \right \rfloor!)$$$$=\left \lfloor n / 5 \right \rfloor + \left \lfloor n / 5^{2} \right \rfloor + \left \lfloor n / 5^{3} \right \rfloor + \cdots$$

故依次计算n / 5,直至n / 5 == 0输出结果。

int FactZero(int n){
    int count = 0;

    while(n > 0){
        count += n / 5;
        n /= 5;
    }
    return count;
}
updatedupdated2022-05-212022-05-21