Программа написана для вычисления значения nCr (C++)

Question

Я вычислил код ниже для вычисления nCr для n значений testCount. Это, кажется, работает отлично подходит для моих ценностей, но testcases хакера земли не удается, связь проблемы http://www.hackerearth.com/problem/golf/minimal-combinatorial/description/ может кто-нибудь сказать мне, что есть потенциал заблуждение в моей логике

`#include <iostream> 
using namespace std; 

int main() 
{ 
    int testCount; 
    int n , r; 
    cin >> testCount; 
    for (int i = 0 ; i < testCount ; i++) 
    { 

     long int a=1; 
     long int b=1; 
     long int c=1; 
     cin >> n; 
     cin >> r; 
     for (int i = n ; i > 1 ; i--) 
     { 
      a = a * i; 
     } 
     for (int i = n-r; i >= 1 ; i--) 
     { 
      b=b*i; 
     } 
     for (int i=r;i >=1;i--) 
     { 
      c=c*i; 
     } 
     long int result=a/(b*c); 
     cout << result<<"\n"; 
    } 

    return 0; 
} 

` упрощена числитель и знаменатель случае

`#include <iostream> 
    using namespace std; 

int main() 
{ 
    int testCount; 
    int n , r; 
    cin >> testCount; 
    for (int i = 0 ; i < testCount ; i++) 
    { 

     long int numerator=1; 
     long int denominator=1; 
     cin >> n; 
     cin >> r; 
     for (int i = n ; i > r ; i--) 
     { 
      numerator = numerator * i; 
     } 
     for (int i = n-r; i >= 1 ; i--) 
     { 
      denominator=denominator*i; 
     } 

     long int result=numerator/denominator; 
     cout << result; 
    } 

    return 0; 

} `

Answer 1

Оба кода могут переполняться (даже если результат должен помещаться в 64 разрядное целое число)

Вы можете попробовать:

std::uint64_t cnr(int n, int r) 
{ 
    std::uint64_t ans = 1; 
    r = std::min(r, n - r); 

    for(int j = 1; j <= r; j++, n--) { 
     // all following do: ans = (ans * n)/j; 
     // but the 2 first cases do some simplifications 
     // to reduce the possibility of overflow 

     if (n % j == 0) { 
      ans *= n/j; 
     } else if (ans % j == 0) { 
      ans = (ans/j) * n; 
     } else { 
      ans = (ans * n)/j; 
     } 
    } 
    return ans; 
}