/**
 * Program to calculate large binomial coefficients 
 * efficiently. As long as the value fits into an
 * unsigned long long int, the program should find
 * it in a relatively short amount of time.
 *
 * Author: Sameer Vijaykar <[email protected]>
 *
 * References:
 * http://blog.plover.com/math/choose.html
 * http://en.wikipedia.org/wiki/Binary_GCD_algorithm
 *
 */
 
#include<stdio.h>
 
typedef unsigned long long int LL;
 
/**
 * Sourced from Wikipedia 
 * http://en.wikipedia.org/wiki/Binary_GCD_algorithm#Implementation_in_C
 */
LL gcd(LL u, LL v)
{
  int shift;
 
  /* GCD(0,x) := x */
  if (u == 0 || v == 0)
    return u | v;
 
  /* Let shift := lg K, where K is the greatest power of 2
     dividing both u and v. */
  for (shift = 0; ((u | v) & 1) == 0; ++shift) {
    u >>= 1;
    v >>= 1;
  }
 
  while ((u & 1) == 0)
    u >>= 1;
 
  /* From here on, u is always odd. */
  do {
    while ((v & 1) == 0)  /* Loop X */
      v >>= 1;
 
    /* Now u and v are both odd, so diff(u, v) is even.
       Let u = min(u, v), v = diff(u, v)/2. */
    if (u < v) {
      v -= u;
    } else {
      LL diff = u - v;
      u = v;
      v = diff;
    }
    v >>= 1;
  } while (v != 0);
 
  return u << shift;
}
 
int main()
{
  int n, k, g, i, i1;
  LL f;
 
  printf("Enter integers n and k: ");
  scanf("%d", &n);
  scanf("%d", &k);
 
  // Check for trivial cases
  if ((n == k) || (n == 1) || (k == 1))
    {
      printf("nCk : 1\n");
      return 0;
    }
 
  /* Beyond this check, everything going into the
     loop will at least be 1 */
 
  f = 1;
 
  /* Pick the smaller denominator */
  k = (k < (n-k) ? k : (n-k));
 
  for (i = 1; i <= k; i++)
    {
      // Compute f = f * (n/i)
 
      if (n % i == 0)
	{
	  f *= (n/i);
	}
      else if (f % i == 0)
	{
	  f = (f/i) * n;
	}
      else
	{
	  g = gcd(f, i);
	  f /= g;
	  i1 = i/g;
	  if (n % i1 == 0)
	    {
	      f *= (n/i1);
	    }
	  else
	    {
	      f = (f*n) / i1;
	    }
	}
 
      n--;
    }
 
  printf("nCk : %lld\n", f);
}