二分搜索 + 组合数 + 找规律

通过找规律和经验感觉，按照斜线划分每一层，因为是找第一次
{:height=”300px” width=”300px”}
{:height=”300px” width=”300px”}
{:height=”300px” width=”300px”}
{:height=”300px” width=”300px”}

#include<iostream>
#include<cstring>
#include<algorithm>

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;i --,j ++)
    {
        res = res * i / j;
        if(res > n) return res;
    }
    return res;
}

bool check(int k)
{
    LL l = 2*k , r = n;

    if(l > r)return false;// 注意，需要补充这个判断。否则n = 1时会出错。

    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;

    cout<< r * (r + 1) / 2 + k + 1 <<endl;//从0，0开始

    return true;
}
int main()
{
    scanf("%d",&n);

    //很重要，通过计算发现中间最多到C(32,16),C(34,17)就大于1e9了,故最多循环16轮！！！
    for(int i = 16;i >= 0;i--)
        if(check(i))break;

    return 0;
}