P2822 组合数问题

    • 3.8K通过
    • 18.5K提交
  • 题目提供者CCF_NOI
  • 标签 数论,数学 组合数学 NOIp提高组 2016 高性能
  • 难度 普及+/提高
  • 时空限制 1s / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

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

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

    其中n! = 1 × 2 × · · · × n

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

    输入输出格式

    输入格式:

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

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

    输出格式:

    t行,每行一个整数代表答案。

    输入输出样例

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

    说明

    【样例1说明】

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

    【子任务】

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