快速求n阶乘在b进制下的末尾0数

\quad 思路就是先将b分解质因数，得到每个质因子及其出现次数，然后计算 n ! n! n!中各个质因子出现次数t，最后将t除以其对应质因子的出现次数，取最小值即可。

long long zeros(long long b, long long n)
{
    map<long long, long long> mp;
    long long res = 1e18;
    // 将b分解质因数，存在mp中
    for(long long i = 2; i * i <= b; i ++ )
        while(b % i == 0) ++ mp[i], b /= i;
    if(b > 1) ++ mp[b];
    // 计算b的每个质因子在n!中出现次数后取最小值
    for(auto &it: mp)
    {
        long long t = 0, temp = n, x = it.first;
        while(temp >= x) t += temp / x, temp /= x;
        res = min(res, t / it.second);
    }
    return res;
}

来个例题，需要用到上述算法结合二分：

#include <iostream>
#include <map>
using namespace std;

long long zeros(long long b, long long n)
{
    map<long long, long long> mp;
    long long res = 1e18;
    // 将b分解质因数，存在mp中
    for(long long i = 2; i * i <= b; i ++ )
        while(b % i == 0) ++ mp[i], b /= i;
    if(b > 1) ++ mp[b];
    // 计算b的每个质因子在n!中出现次数后取最小值
    for(auto &it: mp)
    {
        long long t = 0, temp = n, x = it.first;
        while(temp >= x) t += temp / x, temp /= x;
        res = min(res, t / it.second);
    }
    return res;
}

int main() {
    int t; cin >> t;
    while(t -- )
    {
        long long b, n; cin >> b >> n;
        long long l = 1, r = 1e18;
        while(l < r)
        {
            long long mid = (l + r) / 2;
            if(zeros(b, mid) >= n) r = mid;
            else l = mid + 1;
        }
        if(zeros(b, l) == n) cout << l << endl;
        else cout << -1 << endl;
    }
    return 0;
}