题目描述
下面的图形是著名的杨辉三角形：
如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, ...
给定一个正整数N，请你输出数列中第一次出现N 是在第几个数？
输入格式
输入包含T行，表示T组测试数据。T不超过10。
每行输入一个整数N，N不超过10^9。
输出格式
对于每组测试数据输出一行表示答案。
输入样例 复制
2
3
6输出样例 复制
8
13
思路：
对杨辉三角形进行仔细观察可知道，其中有很多数是重复的，因此我们只需要记录其有效部分。具体规律如下图所示：
还可以发现，对于同一行，列数越大对应的数值也越大。而且某一行的某一列的值为x，在列数不变的情况下，无论行数怎么变大都不会再出现比x小的数；同理再行数不变的情况下列数怎么变大也不会出现比x小的数。并且得知n小于等于10的0次方时，有效列数为0-16列。因此我们可以一列一列的考虑，由于随着行号的变大，数值时单调递增的，其知道了行号、列号对应的数值也就知道了，于是便可以二分行号，使用二分查找的方法来计算本题。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll N;
ll C(int a, int b)//求第i行第j列的值
{ll res = 1;for (ll i = a, j = 1; j <= b; i--, j++){res = res * i / j;if (res > N)//如果中间结果超过N就直接返回return res;}return res;
}
int main()
{cin >> N;for (int k = 16; k >= 0; k--)//一列一列的找{ll l = 2 * k, r = max(N, l), mid;while (l <= r) {//对第k列二分查找行mid = l + (r - l) / 2;//二分行ll CC = C(mid, k);if (CC == N)break;else if (CC > N)r = mid - 1;elsel = mid + 1;}if (C(mid, k) == N){//第mid行、第k列的数就是Ncout << (mid + 1) * mid / 2 + k + 1 << endl;//杨辉三角形的行数符号公差为1的等差数列，故用等差数列求和公式//加上第几列再加上1（因为列从0开始）即可得出该数的位置break;}}return 0;
}
————————————————
版权声明：本文为CSDN博主「zjsru_Beginner」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zjsru_Beginner/article/details/121875334