杨辉三角形
因为对称所以将它分成两半找出规律
#include <iostream>
#include <algorithm>
#include <cstring>
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;
//大于n超过答案没有意义
if(res > n) return res;
}
return res;
}
bool check(int k)//二分法求出当前斜行最大的最小值
{
//右边界必须大于右边界需要判定
int l = k * 2 , r = max(n , l);
while(l < r)
{
int mid = l + r >> 1;
if(C(mid , k) >= n) r = mid;
else l = mid + 1;
}
//如果没有找到答案就返回
if(C(r , k) != n) return false;
cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;
return true;
}
int main()
{
cin >> n;
//最大值是1e9 C(17 , 34)远超过1e9所以取16枚举
for(int i = 16 ; ; i--)
{
if(check(i)) break;
}
return 0;
}