algorithm - 寻找二项式系数除数的智能算法

Question

我对我用来找出非常大数的除数的算法的技巧很感兴趣，更具体地说是“n over k”或 C(n, k)。这个数字本身的范围可能非常大，所以可以这么说，它确实需要将时间复杂度纳入“方程式”。

n over k 的公式是 n!/(k!(n-k)!) 并且我知道我必须尝试利用这样一个事实，即阶乘在某种程度上是一种“递归”——但我还没有读过太多离散数学，所以这个问题既是数学问题又是编程问题自然。

我想我真正在寻找的只是一些引导我朝着正确方向前进的提示 - 我真的被困住了。

Answer 1

首先，您可以从以下事实开始:C(n,k) = (n/k) C(n-1,k-1)。
你可以证明 C(n,k) 可以被 n/gcd(n,k) 整除。
如果 n 是质数，则 n 整除 C(n,k)。
检查 Kummer 定理:如果 p 是素数，n 是正数，k 是正数且 0< k < n 则 p^r 除以 C(n,k) 的最大指数 r 是所需的进位数在基数 p 中减去 n-k。

让我们假设 n>4 :

• 如果 p>n 则 p 不能整除 C(n,k) 因为在基数 p 中，n 和 k 只有一位宽 → 减法中没有进位

• 所以我们必须检查 [2;n] 中的质因数。由于 C(n,k)=C(n,n-k) 我们可以假设 k≤n/2 且 n/2≤n-k≤n

• 对于 [n/2;n] 范围内的质因数，我们有 n/2 < p≤n，或者等效地 p≤n<2p。我们有 p≥2 所以 p≤n < p² 这意味着当 n 以 p 为底写时恰好有 2 个数字并且第一个数字必须是 1。因为 k≤n/2 < p，k 只能是一个数字宽。要么减法为一个进位和一个仅当 n-k< p ⇒ p 除 C(n,k) 时；减法没有进位并且 p 不除 C(n,k)。
  第一个结果是:

  [n-k;n] 中的每个质数都是 C(n,k) 的一个质因数，指数为 1。
  [n/2;n-k] 中没有质数是 C(n,k) 的质因数。

• 在 [sqrt(n); n/2] 我们有 2p≤n< p²，n 在基数 p 中正好是 2 位宽，k< n 意味着 k 最多有 2 位。两种情况:只有一个进位，根本没有进位。仅当 n 的最后一位大于 p 的最后一位时才存在进位 iif n modulo p < k modulo p第二个结果是:

  对于 [sqrt(n);n/2] 中的每个质数 pp 用指数 1 除 C(n;k) 当且仅当 n mod p < k mod pp 不整除 C(n;k) 当且仅当 n mod p ≥ k mod p

• 在 [2; sqrt(n)] 我们必须检查所有素数。只有在这个范围内，素数的指数才会大于 1