题目大意
题目链接
给你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的个数。如果题目中要多次用到素数，那么就采用打表的方式一次求出所有的素数（埃氏筛选法则）。
