Har*_*hal 4 algorithm math logic factorial reasoning
如何计算大数阶乘数的最后几个非零数字？
从大到大,我的意思是n = 10 ^ 100或者其他东西
(编辑:10 ^ 100是n中'n'的大小!)
少数,我的意思是直到7-8 ...
我试着谷歌搜索它,发现这个 -
我试图将其扩展到最后2个非零数字或更多,但失败了......
我发现谷歌上的其他网站显示了如何计算最后x个数字,但不清楚,我无法理解它...
谁能帮我这个？
此外,我无法得到这个,99的最后两个非零数字!是64,所以我认为(199!/ 99!)的最后两个非零数字也应该是64,但它们结果是24,我知道我在这个中犯了一个非常大的逻辑错误,我只是不能把手指放在上面!
进行计算的技巧是你想要找到3个数字.
因子的数量为5,给出10的因子数.然后从5的因子数中减去2的因子数.计算出该幂的2的最后几位数.乘以步骤3中找到的最后几位数字,就完成了.
5的因子数可以如下计算.取n/5(向下舍入).这是多少人的第一个因子为5.然后n/25(向下舍入).有多少人有第二个因子5.继续,直到你完成.
因子2的数量可以类似地仅用序列2,4,8,16来计算.
第三部分很棘手.
但更容易做的是弄清楚所有数字的乘积,包括n哪些是2和5的相对素数.调用该函数f(n).你可以通过乘以相对质数mod 10 ^ k来计算它.并利用这一事实f(i * 10^k + j) = f(j) mod(10^k).
然后你想要的最后几位数f(n)*f(n/2)*f(n/4)*f(n/5)*f(n/8)*f(n/10)*f(n/16)*....有效地生成该序列是汉明数字问题的一个版本.有关如何执行此操作,请参阅https://rosettacode.org/wiki/Hamming_numbers.对于10 ^ 100,在这个序列中仍然只有数万个 - 它受到很好的控制.
关于比率的第二个问题,您需要利用以下两个事实.事实1是你通过减法知道2和5的正确数量因子.第二个是,如果m是相对素10然后m * m^(4 * 10^(k-1) - 1)是1 mod 10^k.所以你现在可以"划分"mod 10 ^ k,并找出答案的每个因素的最后几个术语,不涉及2或5,然后计算出0的数量,以及剩余因子的数量你有2或5个.
这是一个重要的优化.如果你知道f(n)mod 2 ^ 8和5 ^ 8,就不难发现mod 10 ^ 8.但它的值mod这两个可以简化为适度大小的查找表.较大的一个你只需要将它存储到奇数n最多4*390625,但是那些不到800k.(此时你已经乘以不能被5 mod 5 ^ 8整除的事物的所有元素,并且该产品是1.然后模式重复.)如果你使用4字节整数,那就是几MB查找可以很容易地预先计算的表格.
我应该解释为什么这个技巧有效,因为它并不明显,我错了几次.诀窍是相对于5 ^ k的数字形成一个组.意思是每个都有一个逆.因此,如果将它们全部相乘并重新排列,则每个都具有反向超出5 ^ k-1.所以乘以另一个副本再次配对,包括那个讨厌的产品和产品出来1.现在对于我们的f我们只对5不能被5整除的奇数不感兴趣,但奇数不能被5到2*整除5 ^ k,mod 5 ^ k,只是可以被5到5 ^ k整除的那些的重新排列.我们需要2份,因此需要4*5 ^ k.但是我们只需要赔率,因为偶数之后总是和前一个奇数相同.
根据请求,以下是单个示例的工作原理.我会做15的最后3位数!
15! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15
= (1*3*7*9*11*13) * (2*6*14) * (4*12) * (5*15) * (8) * (10)
= (1*3*7*9*11*13) * 2^3*(1*3*7) * 2^4*(1*3) * 5^2*(1*3) * 2^3*(1) * 10*(1)
= 2^11 * 5^3 * f(15) * f(15/2) * f(15/4) * f(15/5) * f(15/8) * f(15/10)
= 2^11 * 5^3 * f(15) * f(15/2) * f(15/4) * f(15/5) * f(15/8) * f(15/10)
= 10^3 * 2^8 * f(15) * f(7) * f(3) * f(3) * f(1) * f(1)
Which leads to the calculation...
256 * 27 * 21 * 3 * 3 * 1 * 1 (mod 1000)
= 368 (mod 1000)
这是正确的,因为15! = 1307674368000.