[蓝桥杯 2021 省 B] 杨辉三角形（二分查找+枚举）

        我们之前学过有关杨辉三角的一些性质，我们知道杨辉三角某个数等于左上和右上两个数相加，但是如果我们按照这个性质依次枚举每行每列，就会很容易超时，因此我们可以枚举列，再二分查找行来寻找满足要求的答案，我们可以先将列数到30，基本涵盖了所有的答案，通过组合数性质来二分查找答案即可

上代码

#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long

using namespace std;

int n;

int C(int a, int b)//C（a，b）表示Cab，a>b。
{
	if(a < b) return 0;
	if(b * 2 > a) b = a - b;//如果b大于a的一半，就将a - b作为b的新值
	int ans = 1;
	for(int i = 0; i < b; i++){
		ans = ans * (a - i) / (i + 1);
		if(ans >= n) return ans;
	} 
	return ans;
} 

signed main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;//输入要查找的数
	if(n == 1){
		cout << 1 << endl;
		return 0;
	}
	//cout << C(30, 20) << endl;
	
	int ans_x = 1e9, ans_y = 1e9;//寻找出现的最小位置，就要先初始化为最大值 
	for(int i = 0; i < 30; i++){//枚举列 
		int l = 2, r = 1e9;//在第二列中为公差为1的等差数列，在1e9行内一定有答案
		
		while(l < r){
			int mid = (r + l) / 2;
			if(C(mid, i) >= n) r = mid;
			else l = mid + 1; 
		}
		
		if(C(l, i) == n){
			if(ans_x > l){
				ans_x = l;
				ans_y = i;
			} 
		}
	} 
	
	cout << ans_x * (ans_x + 1) / 2 + ans_y + 1 << endl;//求出当前答案所在位置，先高斯求和到ans_x再加上当前列数ans_y + 1 
	
	return 0;
}