2

有没有一种有效的方法来找到数字 n，给定一个数字 N（可能大到 10^18），对于某些 n 和 r 等于 nCr？我们如何找到 n 的对应最小值？例如

f(20)=6 (20=6C3)  
f(21)= 7 (21=7C2)  
f(22)= 22 (22=22C1)
4

2 回答 2

0

求最小值 n 与求最大值 r 相同r<=n/2。由于nCr从下方以 为界，因此(2r)Cr=(2r)!/r!要检查的 r 的数量是有限的。10^18最大 r 为 31，因为64C32=1.8*10^18.

对于给定的 r，要找到满足 N=nCr 的 n，可以检查N*r!形式为n*(n-1)*...*(n-r+1)。n 接近(N*r!)^(1/r) + r/2。我认为只需少量检查即可对其进行测试。

更新：

简单的python实现：

from operator import mul  # or mul=lambda x,y:x*y
from fractions import Fraction

def nCk(n,k):
  return int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))
def M(f,t):
  return reduce(mul, range(f,t+1), 1)

def find_n_r(N):
  for r in range(2, 50): # omit 1, since it is trivial solution
    if nCk(2*r, r) > N:
      return False
    Nr = N * M(1,r)
    nn = pow(Nr, 1./r) + r*0.5
    n = int(nn)
    if M(n-r+1,n) == Nr:
      return n, r
    n += 1
    if M(n-r+1,n) == Nr:
      return n, r  

print find_n_r(nCk(31,7))
print find_n_r(nCk(31,7) + 12)

印刷：

(31, 7)
False
于 2013-09-07T22:01:27.510 回答
0

我将给出一个伪代码。该算法在 O((N log N) 2 ) 时间内完成任务。它不够快，但我列出了一些可以显着提高速度的优化。也许有人可以进一步优化这一点。

这里的关键是我们可以确定素数 p 除以 n 的最大幂！对于一些 n,p 而不计算 n! 的值，只需查看 n，在 O(log n) 时间内。我们表示除 n 的 p 的最高幂！通过 hdp(n,p)。hdp(n,p) 可以计算为： hdp(n,p) = floor(n/p) + floor(n/p 2 )+...。因此 hdp(n,p) 可以在 log p中计算n 时间。

首先，我们计算小于或等于 n 的素数列表。然后，我们找到 N 的所有素数。这会更容易，因为您在步骤 1 中计算了最多 N 的素数。令 N = p 1 a 1 p 2 a 2 ...p k a k。

n 的上限和下限由 Ante 在他的解决方案中给出。我们分别称它们为 n max和 n min。然后我们对 n min和 n max之间的所有 n以及 1 到 n 之间的所有 r进行迭代。现在，N = n C r = (n!)/((nr)!*r!) 当且仅当 hdp(n, pi ) - hdp(k, pi ) - hdp(nk, pi ) = a i代表所有 i。因此，最多可以在 O((log n) 2 ) 时间内修剪 nr 对。从最大的主要因素开始应该是更好的主意，因为程度应该很小。

一些优化：

  1. 对于任何 n，您可以找到 r 可以位于的范围，而不是对所有 r 从 1 到 n 进行迭代。使用n C r > (n/r) r等不等式。

  2. 无需考虑小于 p k的 n 值，其中 p k是 N 的最大素因子。

  3. 分别求解n C 2 = N（这只是一个二次方程）。现在，只考虑小于这个解的 n 值。解将是 O(N 1/2 )，因此将时间复杂度降低到 O(N(log n) 2 )。对n C 2 = N 和n C 3 = N 执行此操作会将时间复杂度降低到 O(N 2/3 (log n) 2 ) 等等。

于 2014-12-22T08:31:20.243 回答