拼多多 4.9 笔试

第一题尖峰数组和第二题快乐数没到1小时就做出来了，信心倍增，没想到第3题没看大懂，先做第4题，推导规律搞错了，接下来的时间都花在上面，最后过了5%😅
查了下资料，数论方面的知识，是真的有点难想啊

4.

给定正整数N和M，求N的阶乘N！用M进制数表示时，末尾0的个数，N>=2,M<=1000000
例如N=5，M=10，5！=120，故返回1
数学原理参考链接

#include<iostream>
#include<vector>

using namespace std;

// 求100以内的所有素数
vector initPrimes(int len) {

    vector<int> primes(len + 1, 1);
    primes[0] = 0;
    primes[1] = 1;
    primes[2] = 1;
    for (int i = 2; i <= len; i++) {
        if (primes[i]) {  // 是素数
            for (int j = i + i; j <= len; j=j+i) {
                primes[j] = 0; // 不是素数
            }
        }
    }
    return primes;
}
// 当p是素数时，x!拥有的p因子数量
int getCnt(int p, int x) {
    int res = 0;
    while (x) {
        res += x/p;
        x = x/p;
    }
    return res;
}

int main()
{
    // n! m进制
    int n,m;
    cin>>n>>m;
    vector<int> primes = initPrimes(100);
    /*
    for (int i = 0; i < primes.size(); i++) {
        if(primes[i])cout<<i<<" ";
    }
    */
    // 拆分m为素数组合
    int temp_m = m;
    vector<int> m_primes(100);
    for (int i = 2; i < primes.size(); i++) {
        if(primes[i]) {
            // i是素数
            while (temp_m % i == 0) {
                m_primes[i]++;
                temp_m /= i;
            }
            if (temp_m == 1) break; // 拆分结束
        }
    }

    // getCnt(i,n) 计算拆分出的每个素数 是n的几次幂
    int ans = 1e18;
    for (int i = 2; i < primes.size(); i++) {
        if(m_primes[i]) {
            ans = min(ans, getCnt(i, n)/m_primes[i]); // 幂/素数的个数 取最小值
        }
    }
    cout<<ans<<endl;
    return 0;
}