luogu3927 SAC E#1 - 一道中档题 Factorial

luogu3927 SAC E#1 - 一道中档题 Factorial

​​ v题目背景 数据已修改

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

leoly讲给我们的水题…被icefox秒了

膜膜膜膜orz 自己实在是太弱了x

题意比较好明白

在k进制下末尾为0说明一定出现了k

例如十进制下末尾出现0一定是出现了10或者出现一些2*5

那么我们想一想K进制下有多少个0不就是在n!中 有多少个k的质因子个数取最小即可还得除以在k中出现的次数得到的最小值才是答案

计算的时候每次去找一下这个质因子是否存在然后后面再慢慢筛去平方什么的

#include#includeusing namespace std;long long ans=1e18,n,k;inline long long calc(long long a,long long b){ long long tmp=0; for (a/=b;a;a/=b) tmp+=a;return tmp; }int main(){// freopen("3927.in","r",stdin); scanf("%lld%lld",&n,&k); for (long long i=2;i*i<=k;i++){ long long tmp=0; while (k%i==0) tmp++,k/=i; if (tmp) ans=min(ans,calc(n,i)/tmp); }if (k>1) ans=min(ans,calc(n,k)); printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。