杨辉三角形(c++实现)

题目

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, …

给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入

输入一个整数 N。

输出

输出一个整数代表答案。

样例

输入样例：
6
输出样例：
13

代码

#include<iostream>
using namespace std;
typedef long long LL;
int n;

LL C(int a,int b){
    LL res = 1;
    for(int i=a,j=1;j<=b;j++,i--){
        res = res * i/j;
        if(res>n) return res;
    }
    return res;
}

bool check(int k){
    LL l = k*2,r = max((LL)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;
    LL ans = r*(r+1)/2 + k+1;
    printf("%lld",ans);
    return true;
}



int main(){
    scanf("%d",&n);
    for(int i = 16;;i--){
        if(check(i)) break;
    }
}