SAC E#1

https://www.luogu.org/problem/show?pid=3927

题目背景

数据已修改

SOL君（炉石主播）和SOL菌（完美信息教室讲师）是好朋友。

题目描述

SOL君很喜欢阶乘。而SOL菌很喜欢研究进制。

这一天，SOL君跟SOL菌炫技，随口算出了n的阶乘。

SOL菌表示不服，立刻就要算这个数在k进制表示下末尾0的个数。

但是SOL菌太菜了于是请你帮忙。

输入输出格式

输入格式：

每组输入仅包含一行：两个整数n，k。

输出格式：

输出一个整数：n!在k进制下后缀0的个数。

输入输出样例

输入样例#1：

10 40

输出样例#1：

说明

对于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 （建议大家不要面向数据编程）

思路

质因数分解k，然后查找n!里的质数可以组成多少个k；

代码实现

 1 #include<cmath>
 2 #include<cstdio>
 3 #define LL long long
 4 using namespace std;
 5 const int maxn=1e6+10;
 6 inline LL min_(LL x,LL y){return x<y?x:y;}
 7 LL n,k,ans;
 8 LL s[maxn],ss;
 9 int main(){
10     scanf("%Illd%Illd",&n,&k),ans=n;
11     LL a,b,c;
12     for(LL i=2;i*i<=k;i++)
13     for(LL j=0;;j++){
14         if(j==ss){
15             s[ss++]=i;
16             if(k%i==0){
17                 a=b=0,c=i;
18                 while(k%i==0){k/=i,b++;}
19                 while(n>=c){a+=n/c,c*=i;}
20                 ans=min_(ans,a/b);
21             }
22             break;
23         }
24         if(i%s[j]==0) break;
25     }
26     if(k!=1){
27         a=0,c=k;
28         while(n>=c){a+=n/c,c*=k;}
29         ans=min_(ans,a);
30     }
31     printf("%Illd
",ans);
32     return 0;
33 }