首页 > 拼多多 4.9 笔试
头像
ccchenc
编辑于 2021-04-10 10:53
+ 关注

拼多多 4.9 笔试

拼多多 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;
}

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐