牛客网Wannafly挑战赛25A 因子 数论
正解:小学数学数论
解题报告:
大概会连着写几道相对而言比较简单的数学题,,,之后就会比较难了$QAQ$
所以这题相对而言还是比较水的,,,
首先这种题目不难想到分解质因数趴,,
于是就先对p和n!分别分解下质因数什么的
然后分别考虑每个质因数的指数,答案就是指数之商的min
太显然了不想解释
(感觉好像说得不太清楚,,,随便解释下趴$QAQ$
设$n!=w_{1}^{p_1}\cdot w_{2}^{p_2}\cdot...,p=w_{1}^{q_1}\cdot w_{2}^{q_2}\cdot...$
答案就$min{\frac{p_1}{q_1}}$
$over!$
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rp(i,a,b) for(register ll i=a;i<=b;++i)
ll n,p;
inline ll cl1(ll x){ll sum=0,t=n;while(t){sum+=t/x;t/=x;}return sum;}
inline ll cl2(ll x){ll sum=0;while(p%x==0){sum++;p/=x;}return sum;}
inline ll read()
{
char ch=getchar();ll x=0;bool y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=getchar();
if(ch=='-')ch=getchar(),y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
return y?x:-x;
}
unsigned ll ans=1e18;
int main()
{
n=read();p=read();
rp(i,2,p)if(p%i==0){ans=min(ans,(unsigned ll)cl1(i)/cl2(i));}
printf("%lld\n",ans);
return 0;
}