跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0239. #2361. 「NOIP2016」组合数问题

  • ID: 245
  • 传统题
  • 1000ms
  • 512MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • LibreOJ
  • 中文题面
  • 题目来源
  • 题面语言

#2361. 「NOIP2016」组合数问题

题目描述

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

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

其中 。

小葱想知道如果给定 , 和 ,对于所有的 , 有多少对 满足是 的倍数。

输入格式

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

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

输出格式

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

样例

样例输入 1

1 2
3 3

样例输出 1

1

样例输入 2

2 5
4 5
6 7

样例输出 2

0
7

数据范围与提示


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 130 题。保留原作者与原赛事署名。