P 28 问题 NOIP 项目 二零一六

链接：https://www.luogu.org/problemnew/show/P2822

题目描述

组合数 C(n,m) 表示从 n 个物体中选取 m 个物体的方式数目。举例来说，在 (1,2,3) 的三个物体中选择两个物体时，则有 (1,2)、(1,3) 和 (2,3) 这三种选择方式。根据组合数的定义及排列组合原理可知：我们能推导出计算 C(n,m) 的一般公式如下：C(n,m)=\frac{n!}{(n-m)!} 其中n!=1\times2\times\cdots\times n；特别指出的是当m=0时，默认其值为1

小葱想了解，在给定n、m以及k的值后，在所有满足条件i从0到n且j从0到min(i,m)的情况下，请计算满足组合数C(i,j)能被k整除的数量。

输入输出格式

输入格式：

第一行包含两个整数t和k,其中t表示该测试点共有多少组测试数据k的含义请参考问题描述

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

输出格式：

将输出t行数据，并且每行数据都是一个整数。每个整数表示在所有满足条件的有序对(i,j)中（其中i的取值范围为0到n，并且j的取值范围为0到min(i,m)），满足组合数Cij能被k整除的数量计算结果。