海南省城乡建设厅网站首页,无锡网络公司设计,Wordpress修改主题菜单样式,西安网页制作培训机构问题描述 满足N!的末尾恰好有K个0的最小的N是多少#xff1f; 如果这样的N不存在输出一1。 思路解析
末尾的0是由10产生的#xff0c;而10是由质数2和5产生的
在求阶乘的过程中#xff0c;只要是偶数就会有2#xff0c;而5相对2更少#xff0c;所以对于10的数量我们可以… 问题描述 满足N!的末尾恰好有K个0的最小的N是多少 如果这样的N不存在输出一1。 思路解析
末尾的0是由10产生的而10是由质数2和5产生的
在求阶乘的过程中只要是偶数就会有2而5相对2更少所以对于10的数量我们可以用计算5的数量来代替
所以我们的目标就是求1-N中有多少个5
1-51-101-151-201-25分别有123451个5
不难看出5的个数是最后一个数除以5的商直至不够除5因为有些数包括多个5例如25包含了两个5
def five_count(num):count 0while !(num%5) :#商即为5的个数可以看作是1*52*53*5... 123就是包括前面数字中的5的个数的总和count num//5num num//5return count
因为要求的N要求最小即N一定是5的倍数
但是范围太大即使我们只找5的倍数还是会超时
既然是查找我们便可以利用二分法
l 1
r 10**19while(lr):mid (lr)//2ct five_count(mid)
#一直循环到最接近的结果或符合条件的最终结果if ct k:l mid 1else:r mid
由于二分循环条件是lr,lr可能会造成死循环
所以在最后还要考虑lr的情况
#当rl时
if k five_count(l):print(l)
但是二分法查找的不仅仅是5的倍数因此我们要考虑非5的倍数
对于非5倍数我们考虑最接近该数的小于他的5的倍数换一个说法即考虑该数除5的商不考虑余数
我们只需要把循环条件改成num//5即可
def five_count(num):count 0#不是5的倍数也可以while (num//5):#商即为5的个数可以看作是1*52*53*5... 123就是包括前面数字中的5的个数的总和count num//5num num//5return count
完整代码
import os
import sys# 请在此输入您的代码
#计算从1~num中有多少个5不是5的倍数也可以
def five_count(num):count 0#不是5的倍数也可以while (num//5):#商即为5的个数可以看作是1*52*53*5... 123就是包括前面数字中的5的个数的总和count num//5num num//5return countk int(input())
l 1
r 10**19while(lr):#mid l ((r - l) 1)mid (lr)//2ct five_count(mid)#一直循环到最接近的结果或符合条件的最终结果if ct k:l mid 1else:r mid
#l、r、mid三者最后均相等
#当rl时
if k five_count(l):print(l)
else:print(-1)
