题目背景
数据已修改
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 （建议大家不要面向数据编程）
搞了好久终于AC了
1 //2018-06-06 17:19:52 2 #include3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 10 const long long N = 900001;11 12 long long n, k, base;13 long long a[N], b[N];14 15 long long head;16 void Decom(long long x){17 for(long long i=2; i<=x; i++){18 if(x % i == 0) a[++head] = i, b[head] = 0;19 while(x % i == 0){20 b[head]++;21 x /= i;22 }23 }24 }25 26 long long f(long long x){27 long long tmp = 0;28 while(x >= base){29 tmp += x/base;30 x /= base;31 }32 return tmp;33 }34 35 long long ans = 999999999999999999;36 int main(){37 scanf("%lld%lld", &n, &k);38 Decom(k);39 long long cnt = 9999999999;40 for(long long i=1; i<=head; i++){41 base = a[i], cnt = b[i];42 ans = min(ans, f(n)/cnt);43 }44 45 46 printf("%lld\n", ans); 47 48 return 0;49 }
更新之后更快
//2018-06-06 17:19:52#include#include #include #include #include #include using namespace std;const long long N = 900001;long long n, k, base;long long a[N], b[N];long long head;void Decom(long long x){ for(long long i=2; i*i<=x; i++){ //改成i<=sqrt(x); if(x % i == 0) a[++head] = i, b[head] = 0; while(x % i == 0){ b[head]++; x /= i; } } if(x > 1) a[++head] = x, b[head] = 1; //加上这一行 }long long f(long long x){ long long tmp = 0; while(x >= base){ tmp += x/base; x /= base; } return tmp;}long long ans = 999999999999999999;int main(){ scanf("%lld%lld", &n, &k); Decom(k); long long cnt = 9999999999; for(long long i=1; i<=head; i++){ base = a[i], cnt = b[i]; ans = min(ans, f(n)/cnt); } printf("%lld\n", ans); return 0;}