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 $\frac{n\cdot (n-1)}{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\le 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\le 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()