蓝桥杯 杨辉三角（找规律）

蓝桥杯 杨辉三角（找规律）

 在杨辉三角中，有这样的规律：第i行j列(i,j从0开始)的数，等于C   

且左右对称，即C(a, b) == C(a, a-b)，由中间点向两边递减

每行中间点（每个斜行的开始点）的列数为行数的2倍，因此可以确定枚举时的边界（在枚举第k个斜行（列）时，行数从k开始，所以二分时l=2*k，使得行数mid>=k）

由于n最大1e9，C(34, 17) （第17个斜行）> 1e9, C(32, 16) （第16个斜行）< 1e9，因此只要枚举前16个斜行即可

#include
#include
#include
using namespace std;
typedef long long ll;
int n;
ll c(int a,int b)//求组合数C(a,b) 
{
	ll res=1;
	for(int i=a,j=1;j<=b;i--,j++)
	{
		res=res*i*1.0/j;
		if(res>n) return res;
	}
	return res;
}
bool check(int k)
{
	ll l=2*k,r=n;//让mid>=k 
	while(l>1;
		if(c(mid,k)>=n) r=mid;
		else l=mid+1; 
	}
	if(c(l,k)!=n) return false;
	
	cout<>n;
	for(int k=16;;k--)
		if(check(k))
			break;
	
}

思路借鉴：AcWing 3418. 杨辉三角形 - AcWing