输出格式:

众所周知杨辉三角中华瑰宝他这个三角型是对称的如果我们要求出哪个点是第一次出现的那么一定是在这个三角形的左边我们可以把右半部分删掉完全不用考虑。

这是本题目第一个特点。

现在我们再斜着看一看把斜着的看做一个序列。

第一行数坐标就是(00)第二行从左到右就是1011.....以此类推。

我们再看到中间紫色的这一列数值永远就是C2k^k并且永远是这个数最大我们就可以从这个数开始找起。

而且题目中说到了N最大就是1e9那么C34^171e9

C32^161e9。

所以我只需要找前面16个斜行就行了。

这是本题的第二个特点。

我们现在想想如果一个一个去找的话速度太慢了。

因为序列的单调的这一眼就能看出来而且我们需要找一个特定的在这个值的左边就会太小了在这个值的右边就会太大了就可以将其分为两个部分。

这就符合了我们二分的特点因此我们直接从中间对称轴倒序二分找起即可!这就是本题的第三个特点。

大家一定要好好看看这图仔细去理解

因为我们分析过了我们只需要枚举前16行就可以了那么我们倒序枚举检查一下这一行是不是我们想要的是的话就代表找到了就break退出。

int

n;为什么这么定义呢因为在一个序列之中我们最小的值是上图中紫色的那一些数这些数的特点是C2k^k所以定义他们为最小的左边界节点那么右边界节点就应该是最大的那个数字了但是我们的杨辉三角是无穷的所以我们应该只需要找到题目给出的那个数字就可以了那么这个数一定会在Cn^1的这个地方出现因为这个值就是N。

所以我们把右边界定义为n。

如果l比r都要大就直接返回false不可能在这一行。

因为这个数一定比这一序列的第一个数要小就代表答案的位置在更靠前的序列之中。

进入while循环计算我们的mid值计算我们的Cmid^k让这个数和n比较大小。

如果这个数比n要大或等于的话就代表答案有可能在mid左边也就是更小的那一边所以我们把r赋值给mid。

反之答案比n更小的话那么答案一定在mid的右边也就是更大的一边就让mid1赋值给l。

经过了一轮的while循环判断之后再去计算一下Cr^k看看和答案是否一致如果不一致就是错

bool