题解 | #求表达式 f(n)结果末尾0的个数#

题目链接

题目描述

输入一个自然数 $n$ ，求表达式 $f(n) = 1! \cdot 2! \cdot 3! \cdot \dots \cdot n!$ 的结果末尾有几个连续的 $0$ ？

解题思路

一个数末尾连续 $0$ 的个数，取决于其质因数分解中因子 $10$ 的个数。由于 $10 = 2 \cdot 5$ ，并且在阶乘的质因数分解中，因子 $2$ 的数量总是远多于因子 $5$ 的数量，因此问题等价于求解 $f(n)$ 的质因数分解中总共有多少个因子 $5$ 。

$f(n)$ 是一个连乘积，根据对数性质（这里是指数性质）， $f(n)$ 中因子 $5$ 的总数等于每一项 $k!$ 中因子 $5$ 的数量之和。

令 $Z(k)$ 表示 $k!$ 末尾 $0$ 的个数，也即 $k!$ 中因子 $5$ 的数量。则题目所求为：

$TotalZeros = \sum_{k=1}^{n} Z(k)$

直接计算每个 $Z(k)$ 再求和效率较低。我们可以换一个角度来统计。

考虑 $f(n)$ 的另一种表示形式：

$f(n) = \prod_{k=1}^{n} k! = 1^n \cdot 2^{n-1} \cdot 3^{n-2} \cdot \dots \cdot n^1 = \prod_{k=1}^{n} k^{n-k+1}$

$f(n)$ 中因子 $5$ 的总数，等于 $\sum_{k=1}^{n} (n-k+1) \cdot \text{count\_five}(k)$ ，其中 $\text{count\_five}(k)$ 是数字 $k$ 本身含有的因子 $5$ 的数量。

只有当 $k$ 是 $5$ 的倍数时， $\text{count\_five}(k)$ 才不为 $0$ 。

对于 $k=5, 10, 15, \dots$ ，它们至少含有一个因子 $5$ 。
对于 $k=25, 50, 75, \dots$ ，它们至少含有两个因子 $5$ （其中一个已经在上一层被统计，所以这里要额外统计一次）。
对于 $k=125, 250, \dots$ ，它们至少含有三个因子 $5$ （需要再额外统计一次）。
以此类推。

我们可以按 $5$ 的幂次 ( $5^1, 5^2, 5^3, \dots$ ) 分层来统计贡献：总因子 $5$ 的数量 = (所有 $5$ 的倍数的贡献和) + (所有 $25$ 的倍数的额外贡献和) + (所有 $125$ 的倍数的额外贡献和) + $\dots$

对于 $5^i$ 的所有倍数 $k = j \cdot 5^i \le n$ ，它们每一个都会为总和贡献 $(n-k+1)$ 。

所以，对于给定的 $p = 5^i$ ，它贡献的总和为：

$S_p = \sum_{j=1}^{\lfloor n/p \rfloor} (n - j \cdot p + 1)$

这是一个等差数列求和。令 $N_{mult} = \lfloor n/p \rfloor$ 为 $p$ 的倍数的个数。

$S_p = N_{mult} \cdot (n+1) - p \cdot \sum_{j=1}^{N_{mult}} j$

$S_p = N_{mult} \cdot (n+1) - p \cdot \frac{N_{mult}(N_{mult}+1)}{2}$

最终的答案就是 $S_5 + S_{25} + S_{125} + \dots$ ，直到 $p > n$ 。

算法流程：

初始化总数为 $0$ 。
从 $p=5$ 开始循环。
在循环中，计算当前 $p$ 值下的贡献和 $S_p$ ，并累加到总数中。
更新 $p = p \cdot 5$ 。
当 $p > n$ 时，循环结束。

代码

c++
java
python

#include <iostream>

using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    cin >> n;

    ll total_zeros = 0;
    ll p = 5;
    while (p <= n) {
        ll num_multiples = n / p;
        ll sum_for_p = num_multiples * (n + 1) - p * num_multiples * (num_multiples + 1) / 2;
        total_zeros += sum_for_p;
        
        // 防止 p*5 溢出 long long
        if (p > n / 5) {
            break;
        }
        p *= 5;
    }

    cout << total_zeros << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        long totalZeros = 0;
        long p = 5;
        while (p <= n) {
            long numMultiples = n / p;
            long sumForP = numMultiples * (n + 1) - p * numMultiples * (numMultiples + 1) / 2;
            totalZeros += sumForP;
            
            // 防止 p * 5 溢出 long
            if (p > n / 5) {
                break;
            }
            p *= 5;
        }

        System.out.println(totalZeros);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str:
            return
        n = int(n_str)
        
        total_zeros = 0
        p = 5
        while p <= n:
            num_multiples = n // p
            sum_for_p = num_multiples * (n + 1) - p * num_multiples * (num_multiples + 1) // 2
            total_zeros += sum_for_p
            p *= 5
            
        print(total_zeros)

    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：数论、数学求和
时间复杂度： $\mathcal{O}(\log_5 n)$ 或 $\mathcal{O}(\log n)$ 。循环的次数取决于 $5$ 的幂次增长到 $n$ 所需的步数。
空间复杂度： $\mathcal{O}(1)$ 。只使用了有限个变量来存储中间结果。