我在面试中被问到以下问题:
如何解决这个问题:((3000000!)/(30!)^100000)%(任意素数)
我用蛮力编写了相同的 C 程序，但我确信他没有预料到这一点。对解决方案有什么建议吗？
最佳答案
3000000! = 1*2*3*4*5*..*8*...*16*...*24*...*32*...40*...*64*...*3000000
我们可以计算结果中2的个数吗？是的，2 的每个幂对它的每个倍数贡献一个 2。所以在 n 的因式分解中 2 的总数!是n/2 + n/4 + n/8 + n/16 + n/32 + ...其中 /是整数除法，当项大于 0 时求和:
fnf n f = -- number of `f` factors in `n!`
sum . takeWhile (>0) . tail . iterate (`div` f) $ n
(编写伪代码 in Haskell )。什么时候f*f < n ，会有不止一个词条来总结。对于更大的f s，将只有一个条目求和，即。 n `div` f .
因此 n! 的因式分解被发现为
factfact n = -- factorization of n! as [ (p,k) ... ] for n! = PROD p_i^k_i
let
(ps,qs) = span (\p-> p*p <= n) primes -- (before, after)
in
[(f, fnf n f) | f <- ps] ++
[(f, n `div` f) | f <- takeWhile (<= n) qs]
现在，分解30!有 10 个因素:
> factfact 30
[(2,26),(3,14),(5,7),(7,4),(11,2),(13,2),(17,1),(19,1),(23,1),(29,1)]
它的100000次方就是它的每个因子系数乘以100000。当我们对 3000000! 进行因式分解时，它在 216816 项中的前几项是:
> factfact 3000000
[(2,2999990),(3,1499993),(5,749998),(7,499996),(11,299996),(13,249998),
(17,187497),(19,166665),(23,136361),(29,107142),(31,99998), ...
所以在除法之后，当我们从第一个中减去第二个时，没有缺少也没有完全抵消:
[(2,399990),(3,99993),(5,49998),(7,99996),(11,99996),(13,49998),
(17,87497),(19,66665),(23,36361),(29,7142),(31,99998), ...
所以对于任何小于 3000000 的素数，余数为 0。如果它更大呢，p > 3000000 ？然后，必须使用我们在上面发现的用于此因式分解的模幂 mod p 和乘法 mod p。在 SO 上有很多关于这些的答案。
当然，在生产代码中(对于非惰性编程语言)，我们不会构建中间因式分解列表，而只是逐个处理低于 3000000 的每个素数(惰性语言不需要这样做) ).
关于algorithm - 非常大的数模素数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17887695/