组合数问题
测试数据来自 system/2006
描述
组合数\(C_n^m\)表示的是从n个物品中选出m个物品的方案数。举个例子,从(1, 2, 3)三个物品中选择两个物品可以有(1, 2), (1, 3), (2, 3)这三种选择方法。根据组合数的定义,我们可以给出计算组合数的一般公式:
\(C_n^m = \frac{n!}{m!(n-m)!}\)
其中 n! = 1 x 2 x ... x n。
小葱想知道如果给定n, m和k,对于所有的0 <= i <= n, 0 <= j <= min(i, m)有多少对(i, j)满足\(C_i^j\)是k的倍数。
格式
输入格式
第一行有两个整数t, k,其中t代表该测试点总共有多少组测试数据,k的意义见【问题描述】。
接下来t行每行两个整数n, m,其中n, m的意义见【问题描述】。
输出格式
t行,每行一个整数代表所有的0 <= i <= n, 0 <= j <= min(i, m)有多少对(i, j)满足\(C_i^j\)是k的倍数。
样例1
样例输入1
1 2
3 3
样例输出1
1
样例2
样例输入2
2 5
4 5
6 7
样例输出2
0
7
限制
【子任务】
提示
【样例1说明】
在所有可能的情况中,只有\(C_2^1=2\)是2的倍数。
来源
NOIP 2016 提高组 Day 2 第一题
信息
- ID
- 1148
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者