这是标准的数学题。求N!的非零末位。 这也是标准的BT题，光是N就可以到100位。完全没有直接做的办法。还是看LeeMars的报告吧! 首先考虑某一个N!(N < 10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。由于5的倍数全被提走了，所以这样就不会出现尾数0了。我们先把0..9的阶乘的尾数列出来（注意，5的倍数的位置上是1），可以得到table[0..9] = (1, 1, 2, 6, 4, 4, 4, 8, 4, 6)。对于N < 5，直接输出table[N]即可；对于N > = 5，由于提出了一个5，因此需要一个2与之配成10，即将尾数除以2。注意到除了0 !和1!，阶乘的最后一个非零数字必为偶数（显然，因为在N!的质因数里2的个数要多），所以有一个很特别的除法规律：2 / 2 = 6，4 / 2 = 2，6 / 2 = 8，8 / 2 = 4。比较特殊的就是2 / 2 = 12 / 2 = 6， 6 / 2 = 16 / 2 = 8。这样我们就可以得到如下式子： 代码:           table[N] F(N) = ------------ (0 <= N < 10)           2^([N/5]) 再考虑复杂的。考虑某一个N!(N >= 10)，我们先将所有5的倍数提出来，用1代替原来5的倍数的位置。由于5的倍数全被提走了，所以这样就不会出现尾数0了。我们观察一下剩下的数的乘积的尾数，通过table表，我们发现这10个数的乘积的尾数是6，6 * 6的尾数还是6，因此我们将剩下的数每10个分成一组，则剩下的数的乘积的尾数只与最后一组的情况有关，即与N的最后一位数字有关。由于我们把5的倍数提出来了，N!中一次可以提出[N/5]个5的倍数，有多少个5，就需要有多少个2与之配成10，所以有多少个5，最后就要除以多少个2。注意到除2的结果变化是4个一循环，因此如果有A个5，只需要除(A MOD 4)次2就可以了。A MOD 4只与A的最后两位数有关，很好求算。剩下的5的倍数，由于5已经全部处理掉了，就变成[N/5]!。于是，我们可以得到一个递归关系： 代码:              F([N/5]) * table[N的尾数] * 6 F(N) = ---------------------------------------- (N > 10)                     2^([N/5] MOD 4) 这样我们就得到了一个O(log5(N))的算法，整除5可以用高精度加法做，乘2再除10即 可。整个算法相当巧妙，写起来也比较轻松。 想了好半天，看了好半天，写了好半天....... #include <cstdio>#include <string> typedef struct{    int size, a[110];} LInt; char ch[110];int t[10] ={    1, 1, 2, 6, 4, 4, 4, 8, 4, 6};int f[10] ={    1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; void div5 ( const LInt &l, LInt &r ){    int c = 0, i, t;    memset ( r.a, 0, sizeof ( r.a ) );    for ( i = 0; i < l.size; i ++ )    {        r.a[i] = ( c + l.a[i] * 2 ) % 10;        c = ( c + l.a[i] * 2 ) / 10;    }    if ( c )    {        r.a[i] = c;        i ++;    }    r.size = i;    for ( i = 0; i < r.size - 1; i ++ )    {        r.a[i] = r.a[i + 1];    } r.a[i] = 0;    r.size --;} int mod4 ( const LInt &l ){    int s = l.a[0] + l.a[1] * 10;    return s % 4;} int ld ( const LInt &l ){    if ( l.size == 1 )    {        return f[l.a[0]];    }    else    {        LInt ll;          div5 ( l, ll );        int mod = mod4 ( ll );        int tx = ld ( ll );        int dx = tx * 6 * t[l.a[0]] % 10;        for ( int i = 0; i < mod; i ++ )        {            if ( dx == 2 )            {                dx = 6;            }            else if ( dx == 6 )            {                dx = 8;            }            else            {                dx /= 2;            }        }        return dx;    }}   void proc (){    LInt n;    memset ( n.a, 0, sizeof ( n.a ) );    n.size = strlen ( ch );    for ( int i = 0; i < n.size; i ++ )    {        n.a[i] = ch[strlen ( ch ) - i - 1] - '0';    }    printf ( "%d\n", ld ( n ) );} int main (){    //freopen ( "in.txt", "r", stdin );    //freopen ( "out.txt", "w", stdout );    while ( scanf ( "%s", ch ) != EOF )    {        proc ();    }    return 0;}   2251891 2007-03-02 22:31:05 Accepted 1222 C++ 00:00.01 492K Crux.D

评论