[第33期]非零尾数

leeyong

答案发送到：agstick@126.com，并跟一贴占位

QUOTE:

结果正确,评2分.

[此贴子已经被willin2000于2008-3-22 18:43:28编辑过]

f_qc

算法不好，速度太慢，目前没想到好方法，纯算法问题。凑个数吧

邮件已发送请查收

QUOTE:

位数较大时未能给出结果，得1分。

[此贴子已经被willin2000于2008-3-22 18:44:29编辑过]

HHAAMM

答案已发送到：agstick@126.com，并跟一贴占位.

[em06]忘了考虑长度问题了 有时间再重答一下 我就说竞赛题是不会那么简单的[em04][em04]

想了不少办法 但超过一定的数字就会出错 现没有思路 放弃参加[em04][em04]

还是不对。

[此贴子已经被agstick于2008-3-22 20:56:22编辑过]

agstick

此题其实是到数学题，只要找到其中的规律就不难，要硬来的话，那是解不出来的。

首先考虑某一个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))的算法，对几百位的整数都可以很快解出了。

参考答案：

northwolves

To Luckyguy2008：

首先有一个结论，除了0、1的阶乘以外，大于1的数的阶乘的非零尾数肯定为偶数，而1、6乘以任何偶数，尾数都不变。所以尾数为1和6的数对阶乘的尾数无影响。

先以10的阶乘为例，10!=1*2*3*4*5*6*7*8*9*10，1以及3*7的尾数为1，2*8、4*9、以及6的尾数都为6，所以这些数的乘积为数肯定为6，而其不会影响10!阶乘的尾数，影响10!的尾数只跟5和10有关的倍数有关。

再看任意一个自然数的阶乘，比如123，由上面的结论，1~120的数中，以1、2、3、4、6、7、8、9结尾的数的乘积尾数为6，且不影响最终的尾数。所以123!的非零尾数只与5、10、15、120以及最后的3!（121、122、123）有关。

因为6^n*123!不会影响非零尾数。所以 非零尾数(123!)=非零尾数(5*6*10*6*15*6...*120*6*3!)=非零尾数(30*60*90*...*720*3!)=非零尾数(3!*3^24*24!)

而3^n的尾数，是1、3、9、7的循环，所以由此可以判断24除4余多少来判断3^246的尾数。

所以可以推导出对于任意数N，非0尾数(N!)=非0尾数(mod(n,10)!*3^int(N/5)*int(N/5)!)，如果N的各位大于5，前面int(N/5)!已经把最后一个5算过一遍了，所以在mod(n,10)大于4的情况下可以再除一个5。

经上面分析可以看出，可以用递归来计算。

先定义好2个数组，Data1(0 to 9)=(1,1,2,6,4,4,4,8,4,6)分别代表0~9的尾数的阶乘的尾数，5以上的除了 个5，Data2(0 to 3)=(1，3，9，7)为3^N的尾数。

这样，自定义函数如下：
Public Function NLast(ByVal n)
    If n > 4 Then
        NLast = Data1(Right(n, 1)) * Data2(Right(Int(n / 5), 2) Mod 4) * NLast(Int(n / 5)) Mod 10
    Else
        NLast = Data1(n)
    End If

----------------

分析得太精彩了，学习

northwolves

Luckyguy2008版主的函数可不再预先定义，而直接使用array读入：

Public Function NLast(ByVal n)
If n = 0 Then NLast = 1: Exit Function
NLast = (Array(1, 1, 2, 6, 4, 4, 4, 8, 4, 6)(Right(n, 1)) * Array(1, 3, 9, 7)(Right(Int(n / 5), 2) Mod 4) * NLast(Int(n / 5))) Mod 10
End Function

有没有朋友想过如何取的n!的最后的0前面的15位数字？（n的长度>10000位）

Luckyguy2008

QUOTE:

以下是引用northwolves在2008-3-23 1:27:13的发言：

Luckyguy2008版主的函数可不再预先定义，而直接使用array读入：

Public Function NLast(ByVal n)
If n = 0 Then NLast = 1: Exit Function
NLast = (Array(1, 1, 2, 6, 4, 4, 4, 8, 4, 6)(Right(n, 1)) * Array(1, 3, 9, 7)(Right(Int(n / 5), 2) Mod 4) * NLast(Int(n / 5))) Mod 10
End Function

有没有朋友想过如何取的n!的最后的0前面的15位数字？（n的长度>10000位）

原来Array直接可以得到数组常量，这样改改就只有2条语句了，学习了，谢谢狼版

刚才试了试改成一句话
Public Function NLast(ByVal n)
NLast = IIf(n = 0, 1, (Array(1, 1, 2, 6, 4, 4, 4, 8, 4, 6)(Right(n, 1)) * Array(1, 3, 9, 7)(Right(Int(n / 5), 2) Mod 4) * NLast(Int(n / 5))) Mod 10)
End Function

n=0时结果为1，没有调递归了。但好像递归出不来，死循环了。递归还是好多地方不太理解[em04]

laoyebin

做了10几天也没做出来，终于答案出来了，明天仔细研究研究

彭希仁

QUOTE:

以下是引用northwolves在2008-3-23 1:15:07的发言：

To Luckyguy2008：

首先有一个结论，除了0、1的阶乘以外，大于1的数的阶乘的非零尾数肯定为偶数，而1、6乘以任何偶数，尾数都不变。所以尾数为1和6的数对阶乘的尾数无影响。

先以10的阶乘为例，10!=1*2*3*4*5*6*7*8*9*10，1以及3*7的尾数为1，2*8、4*9、以及6的尾数都为6，所以这些数的乘积为数肯定为6，而其不会影响10!阶乘的尾数，影响10!的尾数只跟5和10有关的倍数有关。

再看任意一个自然数的阶乘，比如123，由上面的结论，1~120的数中，以1、2、3、4、6、7、8、9结尾的数的乘积尾数为6，且不影响最终的尾数。所以123!的非零尾数只与5、10、15、120以及最后的3!（121、122、123）有关。

因为6^n*123!不会影响非零尾数。所以 非零尾数(123!)=非零尾数(5*6*10*6*15*6...*120*6*3!)=非零尾数(30*60*90*...*720*3!)=非零尾数(3!*3^24*24!)

而3^n的尾数，是1、3、9、7的循环，所以由此可以判断24除4余多少来判断3^246的尾数。

所以可以推导出对于任意数N，非0尾数(N!)=非0尾数(mod(n,10)!*3^int(N/5)*int(N/5)!)，如果N的各位大于5，前面int(N/5)!已经把最后一个5算过一遍了，所以在mod(n,10)大于4的情况下可以再除一个5。

经上面分析可以看出，可以用递归来计算。

先定义好2个数组，Data1(0 to 9)=(1,1,2,6,4,4,4,8,4,6)分别代表0~9的尾数的阶乘的尾数，5以上的除了 个5，Data2(0 to 3)=(1，3，9，7)为3^N的尾数。

这样，自定义函数如下：
Public Function NLast(ByVal n)
    If n > 4 Then
        NLast = Data1(Right(n, 1)) * Data2(Right(Int(n / 5), 2) Mod 4) * NLast(Int(n / 5)) Mod 10
    Else
        NLast = Data1(n)
    End If

----------------

分析得太精彩了，学习

分析得不错,可见数学功能深厚.

northwolves

强烈建议此帖的所有参与者学习下面的帖子：

 计算阶乘的 18 位非零尾数