2

我在一次采访中被问到以下问题：

如何解决这个问题：((3000000!)/(30!)^100000)%(任何素数。)

我使用蛮力编写了相同的 C 程序，但我确信他没有预料到这一点。对解决方案有什么建议吗？

4

1 回答 1

1

3000000! = 1*2*3*4*5*..*8*...*16*...*24*...*32*...40*...*64*...*3000000

我们可以计算结果中2的数量吗？是的，每个 2 的幂都会为其每个倍数贡献一个2 。所以n的因式分解中2 s的总数！是整数除法，当它们大于 0 时对项求和：n/2 + n/4 + n/8 + n/16 + n/32 + .../

fnf n f = -- number of `f` factors in `n!`
  sum . takeWhile (>0) . tail . iterate (`div` f) $ n

（在 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 。关于这些，有很多答案。

当然，在生产代码中（对于非惰性编程语言），我们不会构建中间分解列表，而是一个一个地处理低于 3000000 的每个素数（惰性语言不需要这样做）。

于 2013-07-29T05:46:02.147 回答