```cpp
#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
ll read()
{
int num=0;
int flg=1;
char c=getchar();
while(!isdigit(c))
{
if(c=='-')
{
flg=-1;
}
c=getchar();
}
while(isdigit(c))
{
num=(num<<1)+(num<<3)+(c^48);
c=getchar();
}
return num*flg;
}
const int rnd=10;
ll mul(ll a,ll b,ll p)
{
a%=p;
b%=p;
ll ans=0;
while(b)
{
if(b&1)
{
ans=(ans+a)%p;
}
a=(a<<1)%p;
b>>=1;
}
return ans;
}//龟速乘
ll Pow(ll a,ll b,ll p)
{
a%=p;
ll ans=1;
while(b)
{
if(b&1)
{
ans=mul(ans,a,p);
}
a=mul(a,a,p);
b>>=1;
}
return ans;
}
bool miller_rabin(ll n)
{
if(n==2)
{
return true;
}
if(n<2||(!(n&1)))
{
return false;
}
ll m=n-1;
ll k=0;
while(!(m&1))
{
m>>=1;
k++;
}
for(int i=1; i<=rnd; i++)
{
ll a=rand()%(n-1)+1;
ll x=Pow(a,m,n);
for(int j=1; j<=k; j++)
{
ll y=mul(x,x,n);
if(y==1&&x!=1&&x!=n-1)
{
return false;
}
x=y;
}
if(x!=1)
{
return false;
}
}
return true;
}//Miller-Rabin--全球跑的最快的素数判断算法！
int gcd(int a,int b)
{
return b==0?abs(a):gcd(b,abs(a)%b);
}
ll fac[10001],cnt;
//Pollard-ρ素数算子因数分解算法^w^
ll pollard_rho(ll n,ll c)
{
ll i=1,k=2;
ll x1=rand()%(n-1)+1;
ll x2=x1;
while(1)
{
i++;
x1=(mul(x1,x1,n)+c)%n;
ll d=gcd((x2-x1+n)%n,n);
if(1<d&&d<n)
{
return d;
}
if(x2==x1)
{
return n;
}
if(i==k)
{
x2=x1;
k<<=1;
}
}
}//不断调整x1与x2,直到找到ρ循环
void findfac(ll n,ll c)
{
if(n==1)
{
return;
}
if(miller_rabin(n))
{
fac[++cnt]=n;
return;
}
ll p=n;
ll cc=c;
while(p>=n)
{
p=pollard_rho(p,c--);
}
findfac(p,cc);
findfac(n/p,cc);
}
ll n,k,ans;
ll prime[10001];
ll e[10001];
ll tot;
int main()
{
n=read();
k=read();
findfac(k,20031125);
sort(fac+1,fac+cnt+1);
for(int i=1; i<=cnt; i++)
{
if(fac[i]==prime[tot])
{
e[tot]++;
}
else
{
e[++tot]=1;
prime[tot]=fac[i];
}
}
ans=1e12;
for(int i=1; i<=tot; i++)
{
ll num=0;
ll now=prime[i];
if(now>n)
{
break;
}
while(now<=n)
{
num+=n/now;
now*=prime[i];
}
num/=e[i];
ans=min(ans,num);
}
return 0&printf("%lld",ans==1e12?0:ans);
}
```
by first_fan @ 2019-05-11 20:17:13
去你的刚入门
by 萌萌哒小女孩 @ 2019-05-11 20:18:41
+1
by yyk504 @ 2019-05-11 20:26:59
入门切蓝题。。。orz
by yyk504 @ 2019-05-11 20:27:44
@[yyk504](/space/show?uid=128874) 您一定觉得我很菜，因为隔壁咸鱼入门前都在切黑……
by first_fan @ 2019-05-11 20:28:41
@[first_fan](/space/show?uid=126484) 不不不
by yyk504 @ 2019-05-11 20:30:43
@[first_fan](/space/show?uid=126484) 我们机房还有一个比赛常爆零昨天却一次就肝了一紫题。。。
by yyk504 @ 2019-05-11 20:32:42
@[first_fan](/space/show?uid=126484) 我们的机房巨佬。。。
by yyk504 @ 2019-05-11 20:33:30