4077: 【16NOIP提高组】组合数问题

组合数$C_n^m$表示的是从$n$个物品中选出$m$个物品的方案数。举一个例子，从$(1,2,3)$三个物品中选择两个物品可以有$(1,2),(1,3),(2,3)$这三种选择方法。根据组合数的定义，我们可以给出组合数$C_n^m$的一般公式：n$C_n^m=frac{n!}{m!(n-m)}$n其中$n!=1×2×...×n$。n小葱想知道如果给定$n,m$和$k$，对于所有的$0≤i≤n,0≤j≤min(i,m)$有多少对($i,j$)满足$c_i^j$是$k$的倍数。

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

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

1 2
3 3

1