毒瘤数学题：求双阶乘末尾零的个数（附 C++ 代码）

MRC 是一位数学高手，冷老师让他出了一道毒瘤数学题：

求 1!! * 2!! * 3!! * ··· * n!! 的末尾零的个数。

双阶乘定义：

(2k+1)!! = (2k+1) * (2k-1) * (2k-3) * ··· * 1

(2k)!! = (2k) * (2k-2) * (2k-4) * (2k-6) * ··· * 2

输入格式：

一个正整数 n 。

输出格式：

一个整数，表示答案。

样例：

输入： 11

输出： 5

解释： 1!! * 2!! * 3!! * ··· * 11!! = 52563198423859200000

数据范围：

对于 10% 的数据，n <= 10。
对于 50% 的数据，n <= 10^6。
对于 100% 的数据，1 <= n <= 10^18。

解法一：

#include <iostream>
using namespace std;

int countTrailingZeros(int n) {
    int count = 0;
    for (int i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 2; i <= n; i += 2) {
        ans += countTrailingZeros(i);
    }
    cout << ans << endl;
    return 0;
}

时间复杂度分析：

对于每个偶数 i，计算 i!! 的末尾零的个数需要遍历 5 的倍数，时间复杂度为 O(n/5)。总共有 n/2 个偶数，所以整体时间复杂度为 O(n^2)。

对于数据范围 n <= 10^18，此解法复杂度太高，无法在合理时间内计算出结果。需要优化。

优化解法：

观察可知，每个偶数 i 的双阶乘 i!! 都包含了 2 的倍数，而 2 的倍数的个数为 i / 2。所以可以直接计算出所有偶数的 2 的倍数个数之和。

对于每个偶数 i，计算 i!! 的末尾零的个数只需要计算 i 的因子中 5 的个数。因为每两个数中必然有一个数是 5 的倍数，所以可以直接计算出所有偶数的因子中 5 的个数之和。

所以优化后的解法如下：

#include <iostream>
using namespace std;

int countTrailingZeros(int n) {
    int count = 0;
    while (n % 5 == 0) {
        count++;
        n /= 5;
    }
    return count;
}

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 2; i <= n; i += 2) {
        ans += i / 2;
        ans += countTrailingZeros(i);
    }
    cout << ans << endl;
    return 0;
}

优化后的解法时间复杂度为 O(n)。可以在合理时间内计算出结果。

总结：

这道题看似简单，实则隐藏着不少陷阱！本文将带你深入理解双阶乘的概念，并提供两种解法，帮助你轻松应对毒瘤数学题。同时，我们还将分析代码的时间复杂度，并提供优化方案。希望这篇文章对你有所帮助！