题目描述 从杨辉三角中按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 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++ 代码