组合数问题｜NOIP 提高组 2016 第二轮（复赛）真题

1 秒 / 测试点 · 512 MiB

[NOIP 2016 提高组] 组合数问题

题目背景

NOIP2016 提高组 D2T1

题目描述

组合数 $\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $\binom{n}{m}$ 的一般公式：

$$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$

其中 $n!=1\times2\times\cdots\times n$；特别地，定义 $0!=1$。

小葱想知道如果给定 $n,m$ 和 $k$，对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i,j)$ 满足 $k\mid\binom{i}{j}$。

输入格式

第一行有两个整数 $t,k$，其中 $t$ 代表该测试点总共有多少组测试数据，$k$ 的意义见问题描述。

接下来 $t$ 行每行两个整数 $n,m$，其中 $n,m$ 的意义见问题描述。

输出格式

共 $t$ 行，每行一个整数代表所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 中有多少对 $(i,j)$ 满足 $k\mid\binom{i}{j}$。

样例 1

1 2
3 3

样例 2

2 5
4 5
6 7

0
7

说明 / 提示

【样例1说明】

在所有可能的情况中，只有 $\binom{2}{1} = 2$ 一种情况是 $2$ 的倍数。

【子任务】

::cute-table{tuack}

测试点	$n$	$m$	$k$	$t$
$1$	$\le3$	$\le3$	$=2$	$=1$
$2$	^	^	$=3$	$\le10^4$
$3$	$\le7$	$\le7$	$=4$	$=1$
$4$	^	^	$=5$	$\le10^4$
$5$	$\le10$	$\le10$	$=6$	$=1$
$6$	^	^	$=7$	$\le10^4$
$7$	$\le20$	$\le100$	$=8$	$=1$
$8$	^	^	$=9$	$\le10^4$
$9$	$\le25$	$\le2000$	$=10$	$=1$
$10$	^	^	$=11$	$\le10^4$
$11$	$\le60$	$\le20$	$=12$	$=1$
$12$	^	^	$=13$	$\le10^4$
$13$	$\le100$	$\le25$	$=14$	$=1$
$14$	^	^	$=15$	$\le10^4$
$15$	^	$\le60$	$=16$	$=1$
$16$	^	^	$=17$	$\le10^4$
$17$	$\le2000$	$\le100$	$=18$	$=1$
$18$	^	^	$=19$	$\le10^4$
$19$	^	$\le2000$	$=20$	$=1$
$20$	^	^	$=21$	$\le10^4$

对于全部的测试点，保证 $0 \leq n, m \leq 2 \times 10^3$，$1 \leq t \leq 10^4$。

本卷题目

题目可直接阅读。页面加载后可编写 C++ 代码、运行样例并提交在线评测。

正在加载试卷…