题目大意

题目链接
给你n,p两个数，求n的阶乘中p做为因子出现的个数

分析

如果p为质数的话，很容易求出p出现的次数,但是这道题p可能为合数，由数学知识可以知道任意一个数都可以通过质数相乘来得到，所以我就将p分解为多个质数来相乘，同时求出相应的质数在n的阶乘中出现的次数a，同时我也要求出质数在p中出现的次数b（一个质数可以出现多次），最后的结果就是多个质数的a/b值的最小值。

代码

#include <bits/stdc++.h>
#include <stdio.h>
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAX_N=10002;
bool prime[MAX_N];
void getprime()
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;
    for(int i=2;i<MAX_N;i++)
    {
        if(prime[i]==true)
        {
            for(int j=i+i;j<MAX_N;j+=i)
            {
                prime[j]=false;
            }
        }
    }
}
ull number(ull n,int num)
{
    ull sum=0;
    while(n)
    {
        n=n/(ull)num;
        sum+=n;
    }
    return sum;
}
int main()
{
    //freopen("data.txt","r",stdin);
    getprime();
    int p;
    ull n;
    cin>>n>>p;
    ull result=INF;
    for(int i=1;i<=p;i++)
    {
        if(prime[i]&&p%i==0)
        {
            int mid=p;
            int cnt=0;
            while(mid%i==0)
            {
                mid=mid/i;
                cnt++;
            }
            ull res1=number(n,i);
            res1=res1/cnt;
            result=min(result,res1);
        }
    }
    cout<<result<<endl;
    return 0;
}

总结
要明白这道题的思维过程，并能举一反三，求类似这样的问题。同时开数组的时候要注意0的个数。如果题目中要多次用到素数，那么就采用打表的方式一次求出所有的素数（埃氏筛选法则）。