2項係数の計算でオーバーフローを防ぐ

/* 分数 m/n を通分する */
int reduce(int *m, int *n)
{
  int g = gcd(*m, *n);
  *m /= g;
  *n /= g;
}
int enum_combination(int n, int k)
{
  /* C(n,k) = n / k * C(n-1,k-1) というように求める */
  /* 答えがオーバーフローしない範囲の k は、それほど大きくない (k <- n-k の置き換えにより)
     ので、再帰はそれほど深くならない
  */
  if ( n - k < k ) {
    /* n から n-k 個と、n から k 個 の選びかたは同じ */
    return enum_combination(n, n-k);
  } else if ( k == 1 ) {
    return n;
  } else {
    int a = enum_combination(n-1, k-1);
    /* n * a / k は整数。k の因数は、n, a の両方に含まれている可能性がある */
    reduce(&n, &k);             /* n,k の共通因数をなくす */
    assert( a % k == 0 );
    a /= k;                     /* a,k の共通因数をなくす */
    return a * n;
  }
}

正当性については略。

オーバーフローについて。
計算されるべき結果が M 以下だとする。
このとき、計算の途中で ans または div が M を越えることがあるか？

n または k が小さくなると、選びかたの数は小さくなる。
計算の途中で呼ばれる enum_combination が返す値は、戻りのたびに増えるので、
一度 M を越えると、そのあとずっと越える。

1 <= n, 0 <= k <= n で n,k がともに整数のとき、
n * (n-1) * .. * (n-(k-1)) / ( k * (k-1) * .. * 1 ) が整数であることについて。
分子分母の右から j 項の分数に注目し、j に関する帰納法で証明できる。
j = 1 のとき自明。
分子分母で右から j 項分の分数の計算結果を m_j とおき、m_j が整数だと仮定する。（帰納法の仮定）
m_{j+1} = m_j * (n-(k-1)-(j-1)) / (j + 1)
↑の分子はもともと、連続する j+1 個の数の積なので、その j+1 個の数の中にはちょうど 1 つ、 j+1 の倍数が含まれている。
つまり、この分子は j+1 の倍数である。
m_j が整数だと仮定しているので、分母は j+1 のみである。
よって、m_{j+1} は整数。