寻找二项式系数除数的智能算法
Smart algorithm for finding the divisors of a binomial coefficient
我对我用来找出非常大数的除数的算法的技巧很感兴趣，更具体地说是 "n over k" 或 C(n, k)。数字本身的范围可能非常高，所以确实需要将时间复杂度转化为 'equation' 这么说。
n大于k的公式是n！ / (k!(n-k)!) 并且我知道我必须尝试利用阶乘有点 'recursive' 的事实 - 但我还没有读过太多离散数学所以问题既是数学又是编程性质。
我想我真正想要的只是一些让我朝着正确方向前进的提示 - 我真的被困住了。
首先你可以从以下事实开始：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 :
if p>n then p cannot divide C(n,k) because in base p, n and k are only one digit wide → no carry in the subtraction
所以我们必须检查 [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) 的质因数。
in [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] 中的每个素数 p
p 用指数 1 除 C(n;k) 当且仅当 n mod p < k mod p
p 不整除 C(n;k) 当且仅当 n mod p ≥ k mod p
在范围[2; sqrt(n)] 我们必须检查所有素数。只有在这个范围内，质数除数的指数才会大于 1
除数会非常多。如果您只需要素数除数，那么对于每个素数来说这很容易：n! 中 p 的指数是 [n/p] + [n/p^2] + [n/p^3] + ... 其中 [x] 表示 [=16= 的整数部分].只有有限数量的 non-zero 项。您可以重复使用 [n/p^t] 的结果来计算 [n/p^(t+1)].
举个例子，2022!末尾有多少个0？让我们找出 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次。 Check.
所以为了求一个素数p除以一个二项式系数C(n,k)多少次，以上计算n、k和n-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 为底的数字，因此在实践中执行起来可能更容易一些。
我对我用来找出非常大数的除数的算法的技巧很感兴趣，更具体地说是 "n over k" 或 C(n, k)。数字本身的范围可能非常高，所以确实需要将时间复杂度转化为 'equation' 这么说。
n大于k的公式是n！ / (k!(n-k)!) 并且我知道我必须尝试利用阶乘有点 'recursive' 的事实 - 但我还没有读过太多离散数学所以问题既是数学又是编程性质。
我想我真正想要的只是一些让我朝着正确方向前进的提示 - 我真的被困住了。
首先你可以从以下事实开始：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>4 :
if p>n then p cannot divide C(n,k) because in base p, n and k are only one digit wide → no carry in the subtraction
所以我们必须检查 [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) 的质因数。in [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] 中的每个素数 p p 用指数 1 除 C(n;k) 当且仅当 n mod p < k mod p p 不整除 C(n;k) 当且仅当 n mod p ≥ k mod p
在范围[2; sqrt(n)] 我们必须检查所有素数。只有在这个范围内，质数除数的指数才会大于 1
除数会非常多。如果您只需要素数除数，那么对于每个素数来说这很容易：n! 中 p 的指数是 [n/p] + [n/p^2] + [n/p^3] + ... 其中 [x] 表示 [=16= 的整数部分].只有有限数量的 non-zero 项。您可以重复使用 [n/p^t] 的结果来计算 [n/p^(t+1)].
举个例子，2022!末尾有多少个0？让我们找出 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次。 Check.
所以为了求一个素数p除以一个二项式系数C(n,k)多少次，以上计算n、k和n-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 为底的数字，因此在实践中执行起来可能更容易一些。