P2822 组合数问题

    • 4.7K通过
    • 21.2K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 数论,数学 组合数学 NOIp提高组 2016 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    组合数 $C_n^m$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子,从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 $C_n^m$ 的一般公式:

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

    其中 $n!=1\times2\times\cdots\times n$ ;特别地,定义 $0!=1$ 。

    小葱想知道如果给定 $n,m$ 和 $k$ ,对于所有的 $0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )$ 有多少对 $(i,j)$ 满足 $C_i^j$ 是 $k$ 的倍数。

    输入输出格式

    输入格式:

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    1 2
    3 3
    输出样例#1: 复制
    1
    输入样例#2: 复制
    2 5
    4 5
    6 7
    输出样例#2: 复制
    0
    7
    

    说明

    【样例1说明】

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

    【子任务】

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。