b997: NOIP2016 Day2.1.组合数问题
Tags :
Accepted rate : 12人/18人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-02-21 13:18

Content

组合数$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的倍数。

Input

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

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

Output

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

Sample Input
1 2
3 3

2 5
4 5
6 7
Sample Output
1

0
7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1M
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1K
Hint :

【样例1说明】

在所有可能的情况中,只有$C_2^1=2$是2的倍数。

【子任务】

测试点 n m k t
1 3 3 =2 =1
2 =3 ≤10000
3 7 7 =4 =1
4 =5 ≤10000
5 10 10 =6 =1
6 =7 ≤10000
7 20 100 =8 =1
8 =9 ≤10000
9 25 2000 =10 =1
10 =11 ≤10000
11 60 20 =12 =1
12 =13 ≤10000
13 100 25 =14 =1
14 =15 ≤10000
15 60 =16 =1
16 =17 ≤10000
17 2000 100 =18 =1
18 =19 ≤10000
19 2000 =20 =1
20 =21 ≤10000

 

Tags:
出處:
NOIP2016提高组Day2第一题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」