前n项结尾0的个数-JZTXT

题目链接：K-卡特兰数_2023河南萌新联赛第（二）场：河南工业大学 (nowcoder.com)

一开始想到和阶乘末尾0的个数一样的题目，但有点不同，根据公式，一开始的重点完全在公式上了，因为前几项的数太大，猜测公式可以化简，但是当时没学组合数学，又不知道怎么化简嘴都一项，就一直卡着。

后面题解发现和阶乘0的个数确实一样，找出2，5因子数目的最小值，可以递推找，因为（4 * n - 2) / (n + 1) 看作是常数的乘积，有共同的前缀，把相应的因子减掉就是从i - 1到 i 多的因子，最后再求个前缀因子取最小后就是答案

#include<bits/stdc++.h>

using namespace std;
using ull = unsigned long long;
using ll = long long;
using PII = pair<int,int>;
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define endl "\n"
#define pb push_back
const int N=5e6+10;
const int INF=0x3f3f3f3f;
int cnt2[N], cnt5[N];

int main()
{
    int n;
    cin >> n;
    auto f = [&](int x, int t)
    {
        int res = 0;
        while(x % t == 0) res ++, x /= t;
        return res;
    };
    for(int i = 1; i <= n; i ++)
    {
        cnt2[i] = cnt2[i - 1], cnt5[i] = cnt5[i - 1];
        
        cnt2[i] += f(4 * i - 2, 2);
        cnt5[i] += f(4 * i - 2, 5);
        
        cnt2[i] -= f(i + 1, 2);
        cnt5[i] -= f(i + 1, 5);
    }
    for(int i = 1; i <= n; i ++) cnt2[i] += cnt2[i - 1], cnt5[i] += cnt5[i - 1];
    cout << min(cnt2[n], cnt5[n]);
    return 0;
}