Editorial

Computations will be performed using $64$-bit unsigned integers (unsigned long long). Its obvious that

Let’s assign the value of the variable $res$ to $1$. Then multiply it by $\frac{n-i+1}{i}$ for all $i$ from $1$ to $k$. Each time the division by $i$ will yield an integer result, but multiplication can cause overflow. Let $d=GCD(res,i)$. Then let’s rewrite the operation

as

In this implementation we’ll avoid the overflow (the answer is $64$—bit unsigned integer). Note that first we need to perform the division $(n–i+1)/(i/d)$, and then multiply $res/d$ by the resulting quotient.

To compute $C_n^k$, we must run $k$ iterations. But what to do if we want to compute $C_{2000000000}^{1999999999}$? The answer is no more than $2^{64}$, so such input values are possible. As long as $C_n^k=C_n^{n-k}$, then for $n–k<k$ we should assign $k=n–k$.

Example

Consider the next sample:

Let $res=15$, and we need to make a multiplication $res\cdot \frac{4}{3}=15\ast \frac{4}{3}$. Compute $d=GCD(15,3)=3$. So $15\cdot \frac{4}{3}=(15/3)\cdot \frac{4}{3/3}=5\cdot \frac{4}{1}=20$.

Algorithm realization

The gcd function computes the greatest common divisor of $a$ and $b$.

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
  return (!b) ? a : gcd(b,a % b);
}

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

unsigned long long Cnk(unsigned long long n, unsigned long long k)
{
  unsigned long long CnkRes = 1, t, i;
  if (k > n - k) k = n - k;
  for(i = 1; i <= k; i++)
  {
    t = gcd(CnkRes, i);
    CnkRes = (CnkRes / t) * ((n - i + 1) / (i / t));
  }
  return CnkRes;
}

The main part of the program. Read the input data. Sequentially process the test cases.

scanf("%d",&t);
while(t--)
{
  scanf("%llu %llu",&n,&k);
  res = Cnk(n,k);
  printf("%llu\n",res);
}

Java realization

Java does not have unsigned type, so we’ll use BigInteger class.

import java.util.*;
import java.math.*;

public class Main
{
  static BigInteger Cnk(BigInteger n, BigInteger k)
  {
    BigInteger ONE = BigInteger.ONE, CnkRes = ONE;
    if (k.compareTo(n.subtract(k)) > 0) k = n.subtract(k);
    for(BigInteger i = ONE; i.compareTo(k) <= 0; i = i.add(ONE))
      CnkRes = CnkRes.multiply(n.subtract(i).add(ONE)).divide(i);
    return CnkRes;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int tests = con.nextInt();
    while(tests-- > 0)
    {
      BigInteger n = con.nextBigInteger();
      BigInteger k = con.nextBigInteger();
      BigInteger res = Cnk(n,k);
      System.out.println(res);
    }
  }
}

Python realization — comb

To compute the binomial coefficient, we shall use the built-in function $comb(n,k)=C_n^k$.

import math

Read the number of test cases $t$.

t = int(input())
for _ in range(t):

Read the input data of the current test case.

  n, k = map(int, input().split())

Compute and print the answer.

  res = math.comb(n, k)
  print(res)

Python реализация

The Cnk function computes the value of the 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):
    res = res * (n - i + 1) // i
  return res

The main part of the program. Read the number of test cases $t$.

t = int(input())
for _ in range(t):

Read the input data of the current test case.

  n, k = map(int, input().split())

Compute and print the answer.

  res = Cnk(n, k)
  print(res)