Разбор

Если $C_n^k=m$, то $C_n^{n-k}=m$. Достаточно найти решение $k\le n/2$ и вместе с парой $(k,n)$ вывести также пару $(k,n–k)$. При $k=n/2$ эти две пары совпадают.

Пусть $p$ — наименьшее число, для которого $C_{2p}^p>m$. Тогда очевидно что $0\le k<p$.

Зафиксируем такое $k$ что $C_{2k}^k\le m$ и рассмотрим функцию $f(n)=C_n^k$. Тогда при $2k\le n\le m$ функция $f(n)$ является монотонно возрастающей. Следовательно можно решить уравнение $f(n)=m$ бинарным поиском.

Таким образом для решения задачи следует перебрать значения $k(0\le k<p)$ и для каждого такого $k$ решить уравнение $C_n^k=m$ относительно $n$ бинарным поиском. Найденное значение $n$ должно быть целочисленным.

Пример

Рассмотрим уравнение $C_n^k=3003$. Учитывая что $C_{12}^6=924$, а $C_{14}^7=3432$, то нам достаточно перебрать $0\le k\le 6$.

Пусть $k=2$, рассмотрим уравнение $C_n^2=3003$ или $\frac{n\cdot (n-1)}{2}=3003$, $n\cdot (n–1)=6006$. Бинарным поиском в промежутке $4\le n\le 3003$ находим целочисленное решение $n=78$. Учитывая что $n\ne 2\cdot k$, имеем два решения: $C_{78}^2=C_{78}^{76}=3003$.

Реализация алгоритма

Искомые пары будем хранить в векторе пар $res$.

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

Функция Cnk вычисляет значение биномиального коэффициента $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++)
  {

Если на очередной итерации результат превосходит $m$ (мы ищем решение уравнения $C_n^k=m$), то останавливаемся. Таким выходом из функции мы также избежим переполнения.

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

Основная часть программы. Читаем входные данные.

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

Перебираем значение $k$ от $0$ до тех пор пока $C_{2k}^k\le m$.

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

Ищем значение $n(2k\le n\le m)$ бинарным поиском.

    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;
    }

Если $C_{lo}^k=m$, то решение найдено. Заносим в результат одну или две пары решений.

    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(res.begin(),res.end());

Выводим ответ — количество найденных пар и сами пары.

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

Python реализация

Функция Cnk вычисляет значение биномиального коэффициента $C_n^k$.

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

Если на очередной итерации результат превосходит $m$ (мы ищем решение уравнения $C_n^k=m$), то останавливаемся. Таким выходом из функции мы также избежим переполнения.

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

Основная часть программы. Читаем входные данные.

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

Перебираем значение $k$ от $0$ до тех пор пока $C_{2k}^k\le m$.

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

Ищем значение $n(2k\le n\le m)$ бинарным поиском.

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

Если $C_{lo}^k=m$, то решение найдено. Заносим в результат одну или две пары решений.

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

Сортируем пары.

  res.sort()

Выводим ответ — количество найденных пар и сами пары.

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