NOI退役记=_=

SuperOJ-P1941 Factorial Surplus Tail

YYY posted @ 2017年8月23日 14:52 in OI相关 with tags 乱搞 找规律 , 122 阅读
------------------------------------------------
今天小朋友们考试的T2,感觉还有点意思,就想了一下
 
------------------------------------------------
题意:
问0~n内多少个数的阶乘末尾0的个数是偶数(n<=10^18)
------------------------------------------------
题解:
首先我们发现一个数如果不是5的倍数,那么他的答案一定是和上一个数一样的,因此我们首先把n的多余部分处理掉,使数的个数是5的倍数,再把n除以5,(最后记得把答案乘以5))
然后我们就只需要处理0*5,1*5,2*5,...n*5这个序列,我们发现一个数k*5,如果k不是5的倍数,那么他的答案和(k-1)*5是相反的,因此我们还是先把n的多余部分处理掉,使数的个数是5的倍数,然后看如果5个5个一组一共有多少组,每组中k不是5的倍数的数一定会贡献2的答案,因此我们把答案加上组数*2,然后再把n除以5
现在我们只需要处理0*25,1*25,2*25...n*25这个序列,我们发现k*25和k的答案是一样的,因此这个序列和0,1,2...n的答案是一样的,因此我们递归的处理就行了,此时n已经是之前的1/25了
现在我们来证明k*25和k的答案是一样的:
一个数p的答案显然就只和[p/5]+[p/25]+[p/125]+...的奇偶性有关,而25*k只比k多了两项就是[5*k]+[k]=6*k,这是个偶数,不影响奇偶性。
------------------------------------------------
 
 
LOL

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter