资源限制
时间限制：1.0s 内存限制：256.0MB
import java.util.*;
public class Main {
/**
* 组合数和杨辉三角：第i行第j列的数都是组合数C(i, j) （i，j从0开始）
C(n, 1) = n --> 对应从左向右看斜着的第二列！ ---> 一定有解
由于杨辉三角左右对称（C(a, b) == C(a, a-b)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！
1 ---> C(0, 0)
1
1 2 ---> C(2, 1)
1 3 ---> C(2n, n)
1 4 6 ---> C(4, 2)
1 5 10
1 6 15 20 ---> C(6, 3)
n最大1e9， C(34, 17) > 1e9, C(32, 16) < 1e9，因此只要枚举前16个斜行即可
* */
// C(a, b) = a!/(b!(a-b)!) = a * (a-1) .. b / b!
public static long C(long a,long b,long n) {
long res = 1;
for(long i=a,j=1;j<=b;i--,j++) {
//阶乘计算
//得到组合数
res = res * i / j;
if(res > n) return res;
//如果计算结果大于自己之前输入的数字 那么就停止
}
return res;
//返回结果
}
public static boolean check(long k,long n) {
//找左边界 因为需要找第一次出现，所以是左边界模板
//此处是二分模板
// l 是斜线右上角的行数 r 是斜线左下角的行数
long l = 2 * k, r = Math.max(n, l);
while(l<r) {
long mid = (l+r)/2;
if(C(mid,k,n)>=n) r=mid;
else l = mid + 1;
}
//判断找到的值不是与之前输入的值相等
if(C(r,k,n)!=n) {
return false;
}
//找到的值 那么根据公式返回第一次出现的位置
//组合数公式
System.out.print((r+1)*r/2+k+1);
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner reader =new Scanner(System.in);
long n=reader.nextLong();
for(long k=16;;k--) {
//找到数 则停止
if(check(k,n)) break;
}
}
}