阅读背景:

hdu 1066 Last non-zero Digit in N! 数学,求n!最后一位非零数

来源:互联网 

题意:求n!的最后一位非零数。(n很大,需要字符输入)

题解:

我们发现n!末尾的0都是通过5和2想成得到的,我们将n分成20个数一组,最后剩下不足20个数。我们来讨论【1-20】这20个数中含有5的数,只有5,10,15,20是5的倍数,我们还要找4个2来使之乘积得到10(我们从4和12中取,4取了后剩余1,12取了后剩下3),那么剩下数乘积的尾数就是所有尾数的乘积%10了(5的倍数的剩余数先不管),最后剩余的乘积是6,;再讨论【21-40】,5个倍数是25,30,35,40,那么我们取2来自24和32,同样最后剩余的尾数值是6。,以此类推最后每20个数剩余的尾数都是6。我们记这次的操作为fun(n),那么最后要求的尾数6^(n/20)*fun(n/5)*不足20个的尾数。我们发现n!末尾的0都




你的当前访问异常,请进行认证后继续阅读剩余内容。

分享到: