← 返回题目
题库练习 「NOIP2016」组合数问题
← 上一题 下一题 →

A6116 | 「NOIP2016」组合数问题

来源NOIP提高组
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

组合数表示的是从 $ n $ 个物品中选出 $ m $ 个物品的方案数。举个例子，从 $ (1, 2, 3) $ 三个物品中选择两个物品可以有 $ (1, 2) $，$ (1, 3) $，$ (2, 3) $ 这三种选择方法。

根据组合数的定义，我们可以给出计算组合数的一般公式：

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

其中 $ n! = 1 \times 2 \times \cdots \times n $。

小葱想知道如果给定 $ n $，$ m $ 和 $ k $，对于所有的 $ 0 \leq i \leq n $，$ 0 \leq j \leq \min(i, m) $ 有多少对 $ (i, j) $ 满足 $C_i ^ j$ 是 $ k $ 的倍数。

输入格式

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

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

输出格式

$ t $ 行，每行一个整数代表所有的 $ 0 \leq i \leq n $，$ 0 \leq j \leq \min(i, m) $ 有多少对 $ (i, j) $ 满足 $C_i ^ j$ 是 $ k $ 的倍数。

输入输出样例

输入 #1
1 2
3 3
输出 #1
1
输入 #2
2 5
4 5
6 7
输出 #2
0
7
C++ 编辑器
输入
输出