UVA 12683 Odd and Even Zeroes（数学

UVA 12683 Odd and Even Zeroes（数学—找规律）

Time Limit: 1000 MS

In mathematics, the factorial of a positive integer number n is written as n! and is de ned 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
nd how many of the values 0!; 1!; 2!; 3!; : : : ;(n 1)!; n! has even number of trailing zeroes.
Input
Input le contains at most 1000 lines of input. Each line contains an integer n (0 n 10
18
). Input
is terminated by a line containing a `-1'.
Output
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

题意：给定一个数n。判定0! , 1! , 2!, ... , n!这(n+1)个阶乘有多少个末尾0的个数为偶数。 (0<=n<=10^18)

思路：i!末尾0个数取决于阶乘中5的个数。我们以5个数为一个总体。

1(5) 1(10) 1(15) 1(20) 2(25) 1(30) 1(35) 1(40) 1(45) 2(50) 1(55) 1(60) 1(65) 1(70) 2(75) 1(80) 1(85) 1(90) 1(95) 2(100) 1(105) 1(110)

1(115) 1(120) 3(125) 前一个数代表这个数中5的幂，后一个代表那个数。

我们将625曾经的数分组例如以下：

1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3

1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 4

那么哪些段是满足末尾0的个数为偶数呢？我们将第一行的段表示出来,(y)为是，(n)为否

(y)1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 2 (y) 1 (n) 1 (y) 1 (n) 1 (y) 3

我们发现：

(1)已知直到出现第一个5的k次幂的大段,那么直到出现第一个5的(k+1)次幂的大段一定是5的k次幂的大段反复5段，且最后一段的最后

一个元素把k换成(k+1)即为直到出现第一个5的(k+1)次幂的大段。

(2)已知直到出现第一个5的k次幂的大段中每一个小段的y/n情况，那么能够推知第一个5的(k+1)次幂的大段的每一个小段的y/n情况。

1.假设k是偶数。那么接下来的4个段与之前的段情况全然同样。

2.假设k是奇数，那么接下来的4段中，第2和第4段与之前段的情况同样。

第1和第3段与之前段的情况正好相反。

设dp[ i ][ 0 ]表示分组后直到出现第一个5的i次幂时。之前满足末尾0的个数为偶数的段的个数。

dp[ i ][ 1 ] 就是与上述情况相反的偶数的个数

那么

dp[ i ][ 0 ]=5 *dp[ i-1 ][ 0 ] i为奇数；

dp[ i ][ 0 ]=3 *dp[ i ][ 0 ] + 2 *dp[ i ][ 1 ] i为偶数；

dp[ i ][ 1 ] = a [ i - 1 ] - dp[ i ][ 0 ];

预处理完dp数组之后，对于n，我们每次二分找不大于n的最大次幂区间, 最好还是设为k，x= n / a[ k ],那么n -= a[ k ] * x; 同一时候依据k的奇

偶性，更新ans。同一时候我们设了一个变量now记录当前的状态.

#include <iostream>
#include <algorithm>
#include <cstdio>
#define LL long long
using namespace std;
const int maxn=27;

LL n,a[maxn],dp[maxn][2];

void initial()
{
    LL t,sum=1;
    a[0]=1;
    for(int i=1;i<maxn;i++)  a[i]=5*a[i-1];

    dp[0][0]=1,dp[0][1]=0;   //  这个赋值是为了后面好算。不是5倍的 ，以下都是5倍的。
    dp[1][0]=1,dp[1][1]=0;
    for(int i=2;i<maxn;i++)
    {
         if(i%2==0)  dp[i][0]=3*dp[i-1][0]+2*dp[i-1][1];
         else  dp[i][0]=5*dp[i-1][0];
         dp[i][1]=a[i-1]-dp[i][0];
    }

    for(int i=1;i<maxn;i++)
    {
        dp[i][0]*=5;
        dp[i][1]*=5;
    }
}

void solve()
{
     LL ans=0;
     if(n<=4) ans=n+1;
     else
     {
         bool now=0;
         n++;
         while(n)
         {
             int t=upper_bound(a,a+maxn,n)-a-1;
             LL num=n/a[t];
             n=n%a[t];
             if(t==0)   ans+=num*dp[t][now];
             else if(t%2==1)  ans=ans+(num+1)/2*dp[t][now]+num/2*dp[t][now^1];
             else  ans=ans+num*dp[t][now]; n=n%a[t];
             if(t%2==1 && num%2==1)  now^=1;
         }
     }
     cout<<ans<<endl;
}

int main()
{
    initial();
    while(cin>>n)
    {
        if(n==-1)  break;
        solve();
    }
    return 0;
}