NOIP2006组合数问题解答

题目

题目描述

组合数\binom{n}{m} 所表达的含义是从 n 个元素中选取 m 个元素的可能方式数目。例如，在由 (1,2,3) 这三个元素组成的集合中，若从中选取两个元素，则存在 (1,2),(1,3),(2,3) 这三种不同的选取方式。依据组合数的定义，我们可以推导出计算组合数 \binom{n}{m} 的通用表达式如下：

\binom{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) 满足 k|\binom{i}{j}。

• 对于所有测试数据，均满足 0 \leq n, m \leq 2 \times 10^3,1 \leq t \leq 10^4

题解

step 1 暴力做法

针对每个查询请求，通过双重循环遍历n和m的取值，直接应用题设所给的公式计算得出结果，并将其与k进行比较判断

step 2 曰力做法

具备基础数学素养的人士皆知，组