杨辉三角问题，如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列： 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。请给出优化思路及其代码

题目描述

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …

给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入描述:

输入一个整数 N。

输出描述:

输出一个整数代表答案。

示例1

输入

输出

13

思路

比较暴力，直接计算每个数的值，并检查是否等于N，时间复杂度$O(N^2)$，无法通过所有的测试用例

接下来说明并实现第二种解决思路

第二种思路便是二分搜索，我们考虑每一行的第一个数字，这个数字可以由之前的那一行的数字构造而成，因此，这一行是由上一行推得，如果对于这样的数列，我们可以通过下标索引出每一行的第一个数字是什么，进而二分在哪一行，时间复杂度$O(\log N)$

但是如果按照正常的思路来二分索引的话，只能枚举所有的行，计算数字的时间复杂度就又变成了$O(N^2)$

我们换一种思路，假设当前二分到的区域是$[L,R]$, 我们想求出第N个数字是在第几行，对于某一行，设第一个数是$x$，最后一个数是$y$, 那么它们之间的数字个数为$y-x+1$，因此如果第N个数在当前这一行，则一定在$x$和$y$之间

所以当我们知道索引为N的数字在哪一行之后，我们可以通过公式计算出该行第一个数字和最后一个数字的值，然后枚举数字的个数即可求出该数字的索引

关于计算这一行第一个数字和最后一个数字的值，我们注意到杨辉三角的性质，即第N行的所有数字的值，等于$$\frac{N}{i+1}\times C_{N-1}^i$$

我们便可以按照该公式计算

代码

根据上诉的思路，符合题目要求的代码实现