题目链接：

Odd and Even Zeroes

Time Limit: 3000MS

问题描述

In mathematics, the factorial of a positive integer number n is written as n! and is defined as follows:
n! = 1 × 2 × 3 × 4 × . . . × (n − 1) × n =
∏n
i=1
i
The value of 0! is considered as 1. n! grows very rapidly with the increase of n. Some values of n!
are:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
10! = 3628800
14! = 87178291200
18! = 6402373705728000
22! = 1124000727777607680000
You can see that for some values of n, n! has odd number of trailing zeroes (eg 5!, 18!) and for some
values of n, n! has even number of trailing zeroes (eg 0!, 10!, 22!). Given the value of n, your job is to
find how many of the values 0!, 1!, 2!, 3!, . . . ,(n − 1)!, n! has even number of trailing zeroes.

输入

Input file contains at most 1000 lines of input. Each line contains an integer n (0 ≤ n ≤ 1018). Input
is terminated by a line containing a ‘-1’.

输出

For each line of input produce one line of output. This line contains an integer which denotes how
many of the numbers 0!, 1!, 2!, 3!, . . . , n!, contains even number of trailing zeroes.

样例

sample input

2
3
10
100
1000
2000
3000
10000
100000
200000
-1

sample output
3
4
6
61
525
1050
1551
5050
50250
100126

题意

求0!,1!,...,n!里面末尾有偶数个零的数的个数。

题解

将n按五进制展开，发现如果只有当偶数位权上的数的和为偶数时，n的末尾有偶数个0。所以将问题转换成统计小于n的偶数位权为偶数的数有多少个。
这个用数位dp可以解决。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        #define bug(x) cout<<#x<<" = "<
         
          <
          
           0) return dp[len][type]; LL res = 0; int ed = ismax ? arr[len] : 4; for (int i = 0; i <= ed; i++) { if(len&1){ res+=dfs(len-1,type,ismax&&i == ed,iszer&&i==0); } else{ if((i&1)) res+=dfs(len-1,type^1,ismax&&i == ed,iszer&&i==0); else res+=dfs(len-1,type,ismax&&i == ed,iszer&&i==0); } } return ismax ? res : dp[len][type] = res;}LL solve(LL x) { tot = 0; //五进制 while (x) { arr[++tot] = x % 5; x /= 5; } return dfs(tot,0, true,true);}int main() { LL x; memset(dp,-1,sizeof(dp)); while (scanf("%lld",&x)==1&&x!=-1) { printf("%lld\n", solve(x)); } return 0;}