http://codeforces.com/contest/1114/problem/C

The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis.

Aki is fond of numbers, especially those with trailing zeros. For example, the number 92009200 has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers nn and bb (in decimal notation), your task is to calculate the number of trailing zero digits in the bb-ary (in the base/radix of bb) representation of n!n! (factorial of nn).

Input

The only line of the input contains two integers nn and bb (1≤n≤10181≤n≤1018, 2≤b≤10122≤b≤1012).

Output

Print an only integer — the number of trailing zero digits in the bb-ary representation of n!

 

题意：求n!在b进制下末尾0的个数

思路：等价于n!%(b^k)==0的最大k

将b分解为若干素数乘积，记录每个素数含多少次方 b = p1^y1·p2^y2·...·pm^ym.

然后求n!种每个素数含多少次方n ! = p1^x1·p2^x2·...·pm^xm·

答案就是

坑爹的地方好几个，

首先答案最小值minn必须赋很大1e18这样子，因为末尾的0个数可能非常非常多，赋个1<<50这样子都不行。

然后更坑的是爆longlong，不能用当前num比乘之前还小来判溢出，1e11*1e11=1e18（左右）。应该先判能不能乘，再乘，就像下面代码注释了的和注释上面的。

#include<bits/stdc++.h>
using namespace std;
#define maxn 2000000+1000
#define ll long long

ll n,b;
vector<ll> prime;
ll num[maxn];

void divide(ll n)
{
	ll m=sqrt(n+0.5);
	for(ll i=2;i<=m;i++)if(n%i==0)
	{
		prime.push_back(i);
		while(n%i==0)n/=i,num[prime.size()-1]++;
	}
	if(n>1)prime.push_back(n),num[prime.size()-1]++;
}

ll calc(ll n,ll num)
{		
	ll ans=0,num2=num,last=1;
	
	num2=1;
	while(num2<=n/num){num2*=num;ans+=n/num2;}
/*	while(num2<=n)
	{
		if(last>num2)break;
		ans+=n/num2;if(num!=31)cout<<num2<<endl;
		last=num2;
		num2*=num;
	}
*/	return ans;
}

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>b;
	divide(b);
	ll minn=(1LL<<62);
	for(ll i=0;i<prime.size();i++)minn=min(minn,calc(n,prime[i])/num[i]);
	cout<<minn<<endl;
	return 0;
}