c++ - 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