題目大意
題目鏈接
給你n,p兩個(gè)數(shù)沛膳，求n的階乘中p做為因子出現(xiàn)的個(gè)數(shù)
分析
如果p為質(zhì)數(shù)的話，很容易求出p出現(xiàn)的次數(shù),但是這道題p可能為合數(shù)汛聚，由數(shù)學(xué)知識(shí)可以知道任意一個(gè)數(shù)都可以通過(guò)質(zhì)數(shù)相乘來(lái)得到锹安，所以我就將p分解為多個(gè)質(zhì)數(shù)來(lái)相乘，同時(shí)求出相應(yīng)的質(zhì)數(shù)在n的階乘中出現(xiàn)的次數(shù)a倚舀，同時(shí)我也要求出質(zhì)數(shù)在p中出現(xiàn)的次數(shù)b（一個(gè)質(zhì)數(shù)可以出現(xiàn)多次）叹哭，最后的結(jié)果就是多個(gè)質(zhì)數(shù)的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;
}
總結(jié)
要明白這道題的思維過(guò)程痕貌，并能舉一反三风罩，求類(lèi)似這樣的問(wèn)題。同時(shí)開(kāi)數(shù)組的時(shí)候要注意0的個(gè)數(shù)舵稠。如果題目中要多次用到素?cái)?shù)超升，那么就采用打表的方式一次求出所有的素?cái)?shù)（埃氏篩選法則）。
