uva 12683 Odd and Even Zeroes

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 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 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 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;
}

uva 12683 Odd and Even Zeroes

原文：http://blog.csdn.net/u012596172/article/details/40210991