问题描述
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？
输入格式
输入一个整数 N。
输出格式
输出一个整数代表答案。
数据范围
对于 20% 的评测用例，1≤N≤10；
对于所有评测用例，1≤N≤109
输入样例：
6
输出样例：
13
思路
这道题如果想要得满分，需要一点小技巧，详细步骤：
（2）通过上图可以发现每个斜行从右上到左下都是递增的，并且每行从左到右也是递增的。故每个斜行的第一个元素一定是该元素出现的第一个位置，只要从最下面的那个斜行开始枚举，就能找到目标元素。
（3）那么我们接下来要找到前多少个斜行能够包含到最大值 109，通过计算 C1734 要大于 109，并且 C1632 要小于 109 。所以我们只用从第 16 斜行开始往下枚举即可。
代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL n; //求组合数 LL C(LL a, int b) { LL res = 1; for (int i = a, j = 1; j <= b; i--, j++) { res = res * i / j; if (res > n) return res; } return res; } bool check(int k) { //下限是2*k，上限最差是n，当k=1时，C(n,1)=n LL l = 2 * k, r = max(n, l); while (l < r) { LL mid = l + r >> 1; if (C(mid, k) >= n) r = mid; else l = mid + 1; } if (C(r, k) != n) return false; //下标为r的位置前面有r+1行（等差公式得r*(r+1)/2） cout << (LL)r * (r + 1) / 2 + k + 1 << endl; return true; } int main() { cin >> n; //从最大的斜行往前枚举 for (int k = 16;; k--) if (check(k)) break; return 0; }
