题目描述
在杨辉三角二分
样例
#include <bits/stdc++.h>
using namespace std;
int n;
long long Cmb(int a, int b){
long long res = 1;
for (int i = a, j = 1; i > a-b; -- i, ++ j){
res = res * i / j;
if (res > n) return res;
}
return res;
}
bool check(int x, int &diag){
int l = 2*x, r = n;
while (l < r){
int mid = l+r >> 1;
if (Cmb(mid, x) >= n) r = mid;
else l = mid + 1;
}
if (Cmb(l, x) == n) return diag = l, true;
else return false;
}
signed main(){
cin >> n;
int cnt = 17, diag = 0; //因为中间的最大即为最早出现,所以要倒序枚举和二分
while (cnt){
if (check(cnt, diag)) break;
-- cnt;
}
cout << 1ll*diag*(diag+1)/2 + cnt + 1 << "\n";
return 0;
}