1,杨辉三角是对称的,一个数第一次出现必定出现在中轴线的左边。
2,每一个斜线,第一个元素的下标a为2i(i从0开始),上标b为第i个斜线。这里的a正好比行号少1。
我们这里遍历每条斜线,利用二分找到所需要查找的数n。
这里因为这里的a(也就是l)比行数正好少1,b也比列数少1。所以这里是相当于最后求得的行数为l+1,列数就为第几个斜线+1,最后求排在第几个,就是前面的(不算本行)是等差数列公差为1,用高斯算法就行了,然后再加上本行的列数就Ok了。
为什么要从第16行开始而不是其他行呢?
因为显然C(3216)< 1e9,而C(3417)> 1e9,因此我们可以对前16行进行枚举。
注意:我们最后要从第十六个直线开始判断。首先对于左半边杨辉三角来说,每行最大的数一定出现在该行末尾,同时它也是该数最早出现的位置。