原址
题目背景
数据已修改
SOL君（炉石主播）和SOL菌（完美信息教室讲师）是好朋友。
题目描述
SOL君很喜欢阶乘。而SOL菌很喜欢研究进制。
这一天，SOL君跟SOL菌炫技，随口算出了n的阶乘。
SOL菌表示不服，立刻就要算这个数在k进制表示下末尾0的个数。
但是SOL菌太菜了于是请你帮忙。
输入输出格式
输入格式：
每组输入仅包含一行：两个整数n，k。
输出格式：
输出一个整数：n!在k进制下后缀0的个数。
输入输出样例
输入样例#1：
10 40
输出样例#1：
2
说明
对于20%的数据，n <= 1000000， k = 10
对于另外20%的数据，n <= 20， k <= 36
对于100%的数据，n <= 10^12，k <= 10^12
update
1.一组数据
2.K不会==1
3.现在std没有爆long long
4.对数据有问题联系icy （建议大家不要面向数据编程）
思路：
其实就是找 N! 中 因子k 的个数。
理论上我用线性筛是不过的，但是实际上K并没有达到10^12，所以能水过。
#include<iostream>
#include<queue>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int M =1e7+;
long long n,k,sum,tot,t,ans;
long long prime[],cnt;
long long a[],b[];
bool is[M];
void first()
{
long long i,j;
for(i=;i<=M;i++)
{
if(!is[i]) prime[++cnt]=i;
for(j=;j<=cnt;j++)
{
if(i*prime[j]>M) break;
is[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
return ;
}
void work()
{
first(); long long K=k;
for(int i=;i<=cnt;i++)
while(K%prime[i]==)
{
b[i]++;
K/=prime[i];
} ans=1e13+;
for(int i=;i<=cnt;i++)
if(b[i])
{
t=prime[i];
while(t<=n)
{
a[i]+=n/t;
t=t*prime[i];
}
sum=a[i]/b[i];
ans=min(ans,sum);
}
cout<<ans<<endl;
}
int main()
{
scanf("%lld%lld",&n,&k);
work();
return ;
}