如何求阶乘的最后两位非零数字

题目(4星难度):90!末尾一定有许多0,在这一长串0出现之前,最后两位数字是什么?

辅导方法:将题目写给小朋友,让他自行思考解答,

若20分钟仍然没有思路,再由家长进行提示性讲解。

讲解思路:这道题属于数论问题,计算比较繁琐容易出错,解题方法有很多种,

有的方法是对100求余数,有的方法是对25求余数。

过程都需要用到以下两个知识点:设m,n,p,q,a,b都是正整数,p除以n的余数是a,q除以n的余数是b,

(1)若m=p+q,

则m与a+b除以n的余数相同;

(2)若m=p*q,

则m与a*b除以n的余数相同。

下面我们介绍对25求余数的方法,这种方法利用了连续4个数相乘的性质,

总的解题思路是:第一步对5的整数倍分解因数;第二步考虑最后两位数是不是4的整数倍;第三步计算当a是5的整数倍时,

a后面连续4个数的乘积除以25的余数;最后把1到90的数分为两类,分别计算去掉末尾0后除以25的余数。

步骤1:

先思考第一个问题,

对5的整数倍分解因数。

这个问题比较简单,直接计算即可:

5*10*15*…*85*90

=(5^18)*(1*2*…*18)

=(5^18)*(2^9)*(1*3*5…*17)*(1*2*3*…*9)

=(5^21)*(2^16)*(3^4)*(7*9*7*9*11*13*17)。

步骤2:

再思考第二个问题,

90!去掉末尾连续的0后,

最后两位非0的数字是不是4的整数倍?

末尾的0都是由5的整数倍产生的,

由于把1到90分解因数后,

2出现的次数远大于5出现次数,

故末尾连续0的个数等于5出现次数,

也就是步骤1中得到的21。

故90!/(10^21)末尾最后2位数,

就是题目中要求解的数字。

因为2出现的次数远大于5出现次数,

故90!/(10^21)是4的整数倍,

其最后2位数也一定是4的整数倍。

步骤3:

再思考第三个问题,

当a是5的整数倍时,

计算a后连续4个数的乘积除以25的余数。

不妨设a=5k,

则(a+1)(a+2)(a+3)(a+4)

=[(5k+1)(5k+4)][5k+2](5k+3)]

=(25k^2+25k+4) (25k^2+25k+6),

应用余数的第二个知识点可得,

连续4个数除以25的余数为24=4*6。

步骤4:

综合上述几个问题,

考虑原题目的答案。

将1到90的数分为两类,

第一类是5的整数倍与32;

第二类是其余数字去掉32。

由于32=2^5,

根据步骤1的结论可得,

第一类数字乘积的末尾恰有21个0,

则90!/(10^21)可以分为两部分计算,

第一部分是(3^4)*(7*9*7*9*11*13*17),

第二部分是第二类数的乘积。

下面计算90!/(10^21)除以25的余数:

第一部分逐个计算,

可得其除以25的余数是9;

第二部分可以看作18个组,

其中第17组缺少32,

其余各组都是连续4个自然数,

{1,2,3,4}{6,7,8,9},…,{86,87,88,89},

结合步骤3的结论可得,

第二部分除以25的余数等于

(24^17)*31*33*34,

由于24^2=576除以25的余数是1,

故(24^17)*31*33*34除以25的余数,

就等于24*31*33*34除以25的余数,

直接计算可得该余数是18。

由于9*18除以25的余数是12,

故90!/(10^21)除以25的余数也是12。

因此90!/(10^21)的末尾两位可能是:

12,37,62或87。

结合步骤2中4的倍数的结论,

则90!/(10^21)的末尾两位是12,

由于90!末尾有连续21个0,

所以原题的答案是12。

注:1.在所有求余数的过程中,乘积都不用直接计算,只需计算余数的乘积;

2.原题也可以直接对100求余数,用到(10n+k)(10n+10-k)的末两位数字就是k(10-k),感兴趣的朋友组合计算。

原文地址:https://www.cnblogs.com/Eufisky/p/12298253.html