题目描述 从杨辉三角中按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,... 给定一个正整数N，求数列中第一次出现N是第几个数。 输入格式 输入一个整数N。 输出格式 输出一个整数代表答案。 数据范围 1≤N≤10^10 样例 输入样例： 6 输出样例： 13给出C++优化代码和详细注释

算法

如果对一个二项式n≥k≥0在杨辉三角中对应数字记为$C_n^k$

考虑每行的第一个数$C_n^0$, 它是$C_{n-1}^0$上方数字加0, 所以第$i$次出现1时，$n-1$一定是2的幂次方。

$1 1$
$1 2 1$
$1 3 3 1$
$1 4 6 4 1$
$1 5 10 10 5 1$
....
以第五行为例，显然第6个数字为2，第7,8都为1。而第6个数字的位置是第3个，是2的幂，说明前两个1分别位于第2行和第3行的开头，因此第5行的第二个数字是1。

可以通过杨辉三角性质简单推出$C_n^k$的取值公式，如果代入数列中就可以快速求出第$p$项的值。

另外，用二分搜索快速定位第$p$个数字所在的行数$r$，在二项式的迭代计算中，可以通过记录上次夹逼的位置，减少算法复杂度。

时间复杂度 $O(\log^3{N})$

C++ 代码

相关问题

题目描述 下面的图形是著名的杨辉三角形： 如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯ 给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？ 输入描述 输入一个整数 NN。 输出描述 输出一个整数代表答案。

算法1 数学

数列中的数可以通过组合数来计算：第 n 行第 k 个数为 C(n-1, k-1)。因此可以按顺序计算数列中每个数，直到第一个大于等于 N 的数出现为止。

时间复杂度：O(N^2)

C++ 代码

算法2 二分查找

观察数列，可以发现它是逐行递增的，因此可以考虑使用二分查找。具体地，在数列中找到第一个大于等于 N 的数。至于如何找到第 n 行第 k 个数，可以使用公式 C(n-1, k-1)，也可以使用递推式 C(n, k)=C(n-1, k-1)+C(n-1, k)来计算。

时间复杂度：O(log^2 N)

C++ 代码

杨辉三角问题，如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \cdots1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯ 给定一个正整数 NN，请你输出数列中第一次出现 NN 是在第几个数？ 输入描述 输入一个整数 NN。 输出描述 输出一个整数代表答案。 输入输出样例 示例 1 输入 6 copy 输出 13 copy 评测用例规模与约定 对于 20%20​​ 的评测用例，1\leq N\leq 101≤N≤10​； 对于所有评测用例，1\leq N\leq 10000000001≤N≤1000000000。请给出思路

题目大意

给定一个正整数 N，按照杨辉三角的顺序将其中所有的数依次排列成一行，求第一次出现 N 的位置。

思路分析

首先我们需要知道杨辉三角的性质，即第 n 行有 n 个数，每行的两端数为 1，第 n 行的第 m 个数等于第 n-1 行的第 m-1 个数加上第 m 个数，即：

$$C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}$$

杨辉三角规律图

根据以上杨辉三角的规律，我们可以生成杨辉三角，并且也可以找出第一次出现 N 的位置。具体做法如下：

- 生成杨辉三角。我们可以使用二维数组来存储杨辉三角，其中第 i 行第 j 列的值表示杨辉三角中第 i 行第 j 列的数。
- 遍历杨辉三角，找到第一次出现 N 的位置并记录。我们可以从第一行第一列开始遍历，如果当前数字等于 N，则记录该数字的位置即可。

代码实现