c++中大数的组合

Question

如何在C++中计算大数的组合？（例如，nCr n=1000 和 r=500）要求是组合的最后 9 位数字。我尝试使用 long long int 变量，但我的代码仍然能够解决和显示 50C19 的最后 9 位数字，但不超过这个数字。

const long int a = 1000000000;
long long int ncr(int n,int r)  
{
 long long int fac1 = 1,fac2=1,fac;
 for(int i=r;i>=1;i--,n--)
    {
        fac1 = fac1 * n;
        if(fac1%i==0)
            fac1 = fac1/i;
        else
            fac2 = fac2 * i;
    }
 fac = fac1/fac2;
 return fac%a;
}

Answer 1

只要将分子的因数存入一个数组中，并在可能的情况下将分母的每个因数分开即可。最后取减少分子的乘积 mod 10^9.

这是您的特定示例的一些代码。你需要写一个gcd()函数。

int a[] = { 1000,999,...,501 }; // numerator factors

for (int b = 2; b <= 500; b++) {
  int x = b;
  for (int i = 0; i < 500; i++) {
    int d = gcd(x, a[i]);
    if (d > 1) {
      x = x / d;
      a[i] = a[i] / d;
      if (x <= 1) break;
    }
  }
}

// take the product of a[] mod 10^9

int ans = 1;
for (int i = 0; i < 500; i++) {
  ans = (ans * a[i]) % 1000000000;
}
// ans = C(1000,500) mod 10^9

此处提供了对其他技术的很好的讨论：

http://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m

c++中大数的组合

Combinations of large number in c++

c++

combinations