算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
///这个题的思路就是:认清楚杨辉三角形的一些特征比如C(2K,K)
///代表这个数是在第2K+1行,且是从左到右第K+1个数字
ll n;///在杨辉三角中数字n一定会出现在C(n,1)上,但不一定是第一个出现的
ll C(ll a, ll 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 query(int h){///固定的列数,就在0~17内
ll l = 2 * h, r = max(n, l); //r是最大行,l是本身在1e9内的行
while(l < r){
ll mid = l + r >> 1;
if(C(mid, h) >= n) r = mid;//值大了,就向上移动行数,减小r
else l = mid + 1;
}
if(C(r, h) != n) return false;
//最终是在第r行,第h列,都是从0开始算的,这个数前面有r行
cout << r * (r + 1) / 2 + h + 1;
return true;
}
int main(){
cin >> n;
for(int i = 17; i >= 0; -- i){//最坏循环17次,每次都是进行二分查找
if(query(i)) break;
}
return 0;
}