毒瘤数学题：求双阶乘之积的后缀0个数

毒瘤数学题：求双阶乘之积的后缀0个数

MRC是一位数学高手，于是冷老师让他出几套题。MRC经过思考，想出了一道绝世毒瘤题：

求

1!! * 2!! * 3!! *···*n!!

WXY：'好好好，你这么出题是吧，好好好。'

作为凉心出题人，WXY把题目简化了，只需要输出上面式子的答案的后缀 0 的个数即可。

双阶乘：

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

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

输入格式

一个正整数 n 。

输出格式

一个整数，表示答案。

答案可能很大，可使用 __int128。

样例 #1

样例输入 #1

11

样例输出 #1

5

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

提示

数据范围

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

用C++做出这道题（附代码）

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            int num = i;
            while (num % 2 == 0) {
                cnt++;
                num /= 2;
            }
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

解题思路

根据题目描述，我们需要计算1!! * 2!! * 3!! *···*n!!中后缀0的个数。

双阶乘的计算规则是，对于奇数2k+1，可以将其转化为(2k+1) * (2k-1) * (2k-3) * ··· * 1的形式；对于偶数2k，可以将其转化为(2k) * (2k-2) * (2k-4) * (2k-6) *··· * 2的形式。

我们可以发现，每个偶数都会贡献一个2，而每个能被5整除的数都会贡献一个5。

所以，我们只需要计算1到n中有多少个偶数，以及有多少个能被5整除的数，取二者的较小值即可。

以上是用C++实现的代码，使用一个变量cnt来记录后缀0的个数。遍历1到n，对于每个偶数，将其不断除以2，直到不能整除为止，每次除2都会增加一个后缀0的个数。对于能被5整除的数，同样将其不断除以5，每次除5都会增加一个后缀0的个数。最后输出cnt即可。

由于题目给出的数据范围较大，我们可以使用__int128类型来保存结果。如果使用其他语言，可以使用大整数运算库来进行计算。