目录

题目描述：

解题思路：

备注知识点：

代码详解：

---

题目描述：

解题思路：

所求为第一次出现的数字

因为杨辉三角沿中间轴对称

故只需考虑最左边的数字

因为杨辉三角对于每一列从小到大递增

对于每一行从小到大递增（对齐之后看）

故只需从最右边的最上面的数字查看

这样第一个找到的数一定是最先出现的数

备注知识点：

1.对于杨辉三角按对称轴只取最左边，对齐之后，从0开始，每一个数都可以表示为组合数C(x,y)的值（表示第x+1行，第y+1列的数）

2.可以推算出组合数的式子即  =  +  ，杨辉三角的性质（一个数由上面的数和上面的左边的数相加所得）

代码详解：

#include<iostream>
using namespace std;
typedef long long ll;ll n;ll C(ll x,ll y){//求组合数if(x==y||y==0) return 1;ll ans=1;y=min(x-y,y);//取最小的yfor(ll i=1;i<=y;i++){ans=ans*(x-i+1)/i;if(ans>n) return ans;//对于大于n的数直接跳过}return ans;
}bool check(ll k){ll l=2*k;ll r=max(l,n);//防止出现r<l的情况while(l<r){ll mid=l+r>>1;if(C(mid,k)<n) l=mid+1;else r=mid;}if(C(l,k)!=n) return 0;//判断是否相等else {cout<<(l+1)*l/2+k+1;return 1;}
}int main(){cin>>n;for(ll i=16;i>=0;i--){if(check(i)) break;}return 0;
}