P2822 [NOIP 2016 Senior] Binomial Coefficient Problem

NOIP 2016 Senior D2T1.

The binomial coefficient $\binom{n}{m}$ represents the number of ways to choose $m$ items from $n$ items. For example, when choosing two items from three items $(1, 2, 3)$, there are three choices: $(1, 2)$, $(1, 3)$, and $(2, 3)$. By definition, the general formula for computing the binomial coefficient $\binom{n}{m}$ is: $$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$ where $n!=1\times2\times\cdots\times n$. In particular, $0!=1$. Xiaocong wants to know, given $n$, $m$, and $k$, among all $0 \leq i \leq n$, $0 \leq j \leq \min \left ( i, m \right )$, how many pairs $(i, j)$ satisfy $k \mid \binom{i}{j}$.

The first line contains two integers $t, k$, where $t$ is the number of test cases in this testdata, and $k$ is as described in the problem. Each of the next $t$ lines contains two integers $n, m$, where $n$ and $m$ are as described in the problem.

Output $t$ lines. Each line contains a single integer representing how many pairs $(i, j)$ among all $0 \leq i \leq n$, $0 \leq j \leq \min \left ( i, m \right )$ satisfy $k \mid \binom{i}{j}$.

Sample 1 Explanation. Among all possible cases, only $\binom{2}{1} = 2$ is a multiple of $2$. Subtasks. | Testpoint | $n$ | $m$ | $k$ | $t$ | |:-:|:-:|:-:|:-:|:-:| | $1$ | $\le 3$ | $\le 3$ | $=2$ | $=1$ | | $2$ | ^ | ^ | $=3$ | $\le 10^4$ | | $3$ | $\le 7$ | $\le 7$ | $=4$ | $=1$ | | $4$ | ^ | ^ | $=5$ | $\le 10^4$ | | $5$ | $\le 10$ | $\le 10$ | $=6$ | $=1$ | | $6$ | ^ | ^ | $=7$ | $\le 10^4$ | | $7$ | $\le 20$ | $\le 100$ | $=8$ | $=1$ | | $8$ | ^ | ^ | $=9$ | $\le 10^4$ | | $9$ | $\le 25$ | $\le 2000$ | $=10$ | $=1$ | | $10$ | ^ | ^ | $=11$ | $\le 10^4$ | | $11$ | $\le 60$ | $\le 20$ | $=12$ | $=1$ | | $12$ | ^ | ^ | $=13$ | $\le 10^4$ | | $13$ | $\le 100$ | $\le 25$ | $=14$ | $=1$ | | $14$ | ^ | ^ | $=15$ | $\le 10^4$ | | $15$ | ^ | $\le 60$ | $=16$ | $=1$ | | $16$ | ^ | ^ | $=17$ | $\le 10^4$ | | $17$ | $\le 2000$ | $\le 100$ | $=18$ | $=1$ | | $18$ | ^ | ^ | $=19$ | $\le 10^4$ | | $19$ | ^ | $\le 2000$ | $=20$ | $=1$ | | $20$ | ^ | ^ | $=21$ | $\le 10^4$ | Constraints. For all testdata, it is guaranteed that $0 \leq n, m \leq 2 \times 10^3$, $1 \leq t \leq 10^4$. Translated by ChatGPT 5