SuperOJ-P1941 Factorial Surplus Tail
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
------------------------------------------------
今天小朋友们考试的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，这是个偶数，不影响奇偶性。
------------------------------------------------
评论 (0)
