题目地址:https://codeforces.com/contest/1114/problem/C

题意


给出十进制的数n,和要转换的进制b,求n!转化成b进制之后末尾有多少个0

 

解题思路


就是求最大的k,使  

对b质因子分解: ,记录对应的个数(用map存对应关系,vector存

对n!质因子分解:(后面的x1...xn在求结果的时候不用考虑)

ans=min(),表示n!最多可以整除b的ans次方,即结果

 

ac代码


#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 1005
typedef long long ll;
using namespace std;
ll n,b,ans=2e+18;
vector<ll> p;
map<ll,ll> m;//质因子对应的个数
void solve_b() //对b质因子分解
{
    for(ll i=2;i*i<=b;i++)
    {
        if(b%i==0)
        {
            p.push_back(i);
            while(b%i==0)
            {
                m[i]++;
                b/=i;
            }
        }
    }
    if(b!=1)
    {
        m[b]++;
        p.push_back(b);
    }
}
ll numn(ll x)//返回n中质因子的个数
{
    ll num=0,a=n;
    while(a/x)
    {
        num+=a/x;
        a/=x;
    }
    return num;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%lld %lld",&n,&b);
    solve_b();
    for(int i=0;i<p.size();i++)
        ans=min(ans,numn(p[i])/m[p[i]]);
    printf("%lld\n",ans);
    return 0;
}