#NOIPS2016D. 组合数问题

组合数问题

题目描述

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

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

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

其中 n!=1×2××nn! = 1 \times 2 \times \cdots \times n

小葱想知道如果给定 nnmmkk,对于所有的 0in0 \leq i \leq n0jmin(i,m)0 \leq j \leq \min(i, m) 有多少对 (i,j)(i, j) 满足 CijC_i ^ jkk 的倍数。

输入格式

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

接下来 tt 行每行两个整数 nnmm,其中 nnmm 的意义见「题目描述」。

输出格式

tt 行,每行一个整数代表所有的 0in0 \leq i \leq n0jmin(i,m)0 \leq j \leq \min(i, m) 有多少对 (i,j)(i, j) 满足 CijC_i ^ jkk 的倍数。

1 2
3 3
1
2 5
4 5
6 7
0
7

数据范围与提示

对于 100%100\% 的数据,3n3 \leq nm2×103m \leq 2\times 10^32k212 \leq k \leq 211t1041 \leq t \leq 10^4