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

Question

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

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

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

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 是质数，na 正数和 ka 正数且 0< k < n 那么 p^r 除以 C(n,k) 的最大指数 r 是所需进位的数量以 p 为底的减法 nk。

让我们假设 n>4 ：

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

• 所以我们必须检查 [2;n] 中的素数除数。由于 C(n,k)=C(n,nk) 我们可以假设 k≤n/2 和 n/2≤nk≤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 只能是一个数字宽。只有当 nk< p ⇒ p 除以 C(n,k) 时，减法作为一个进位和一个；减法没有进位并且 p 不除 C(n,k)。
  第一个结果是：

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

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

  对于 [sqrt(n);n/2] 中的每个素数 p，p 将 C(n;k) 除以指数 1 当且仅当 n mod p < k mod p p 不除 C(n;k) 且当 n mod p ≥ k模p

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

Answer 2

会有很多除数。如果您只需要素数除数，那么对于每个素数来说这很容易：in 的指数p是n!where[n/p] + [n/p^2] + [n/p^3] + ...表示[x]的整数部分x。只有有限数量的非零项。您可以重复使用 的结果[n/p^t]来计算[n/p^(t+1)]。

例如，末尾有多少个零2022!？5让我们找到划分的次数2022!

[2022/5] = 404
[404/5] = 80
[80/5] = 16
[16/5] = 3
[3/5] = 0

所以 2022 年有 5 个除法！404+80+16+3=503 次，而且 2 显然比这多，所以 10=5*2 做了 503 次。检查。

因此，为了找出素数p除以二项式系数 的次数，请分别对和C(n,k)进行上述计算n，然后减去：kn-k

the exponent of p in C(n,k) = (the exponent of p in n!) - 
                              (the exponent of p in k!) -
                              (the exponent of p in (n-k)!)

现在对所有小于或等于 sqrt(n) 的素数重复此操作，就完成了。

这基本上与其他答案中的计算相同，但没有明确计算以 p 为底的数字，因此在实践中执行起来可能会更容易一些。