Binomial coefficients (Editorial)

If C_n^k = m, then C_n^{n - k} = m. It is sufficient to find the solution for k \le n / 2 and, along with the pair $(k,n)$, also print the pair (k, n – k). For k = n / 2 these two pairs coincide.

Let $p$ be the smallest number for which C_{2p}^p > m. Then it is obvious that 0 \le k < p.

Choose $k$ such that C_{2k}^k \le m and consider the function f(n) = C_n^k. Then for 2k \le n \le m, the function $f(n)$ is monotonically increasing. Therefore, you can solve the equation f(n) = m by binary search.

To solve the problem, one should iterate over the values of k~(0 \le k < p), and for each such $k$, solve the equation C_n^k = m relatively $n$ with binary search. The found value of $n$ must be an integer.

Example

Consider the equation C_n^k = 3003. Given that C_{12}^6 = 924 and C_{14}^7 = 3432, it is sufficient to iterate over 0 \le k \le 6.

Let k = 2, consider the equation C_n^2 = 3003 or {n \cdot (n - 1) \over 2} = 3003, n \cdot (n – 1) = 6006. By binary search in the interval 4 \le n \le 3003, we find an integer solution n = 78. Since n \ne 2 \cdot k, we have two solutions: C_{78}^2 = C_{78}^{76} = 3003.

Algorithm realization

Store the required pairs in the vector of pairs $res$.

vector<pair<long long,long long> > res;

The Cnk function computes the value of binomial coefficient C_n^k.

long long Cnk(long long n, long long k)
{
  long long i, Res = 1;
  if (k > n - k) k = n - k;
  for(i = 1; i <= k; i++)
  {

If at the next iteration the result exceeds $m$ (we are searching for a solution to the equation C_n^k = m), then stop computations. Exiting the function at this point avoids overflow.

    if (1.0 * Res * (n - i + 1) / i > m) return m + 1;
    Res = Res * (n - i + 1) / i;
  }
  return Res;
}

The main part of the program. Read the input data.

scanf("%d",&tests);
while (tests--) 
{
  res.clear();
  scanf("%lld",&m);

Iterate over the values of $k$ from $0$ until C_{2k}^k ≤ m.

  for(k = 0; Cnk(2*k,k) <= m; k++)
  {

Find the value of n~(2k \le n \le m) using binary search.

    long long lo = 2*k, hi = m;
    while (lo < hi) 
    {
      long long n = (lo + hi) / 2;
      if (Cnk(n,k) < m) lo = n + 1; else hi = n;
    }

If C_{lo}^k = m, then a solution is found. Include one or two pairs of solutions in the result.

    if (Cnk(lo,k) == m)
    {
      res.push_back(make_pair(lo,k));
      if (lo != 2*k)
        res.push_back(make_pair(lo,lo - k));
    }
  }

Sort the pairs.

  sort(res.begin(),res.end());

Print the answer — the number of found pairs and the pairs themselves.

  printf("%d\n",res.size());
  for(i = 0; i < res.size(); i++)
    printf("(%lld,%lld) ", res[i].first,res[i].second);
  printf("\n");
}

Python realization

The Cnk function computes the value of binomial coefficient C_n^k.

def Cnk(n, k):
  Res = 1
  if k > n - k:
    k = n – k
  for i in range(1, k + 1):

If at the next iteration the result exceeds $m$ (we are searching for a solution to the equation C_n^k = m), then stop computations. Exiting the function at this point avoids overflow.

    if Res * (n - i + 1) // i > m:
      return m + 1
    Res = Res * (n - i + 1) // i
  return Res

The main part of the program. Read the input data.

tests = int(input())
for _ in range(tests):
  res = []
  m = int(input())

Iterate over the values of $k$ from $0$ until C_{2k}^k ≤ m.

  k = 0
  while Cnk(2 * k, k) <= m:

Find the value of n~(2k \le n \le m) using binary search.

    lo, hi = 2 * k, m
    while lo < hi:
      n = (lo + hi) // 2
      if Cnk(n, k) < m:
        lo = n + 1
      else:
        hi = n

If C_{lo}^k = m, then a solution is found. Include one or two pairs of solutions in the result.

    if Cnk(lo, k) == m:
      res.append((lo, k))
      if lo != 2 * k:
        res.append((lo, lo - k))
    k += 1

Sort the pairs.

  res.sort()

Print the answer — the number of found pairs and the pairs themselves.

  print(len(res))
  for item in res:
    print(f"({item[0]},{item[1]})", end=" ")
  print()