详细请查看注释
参考代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
/*
组合数和杨辉三角：第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个斜行即可！
性质：
1. 每一斜行从上到下递增
2. 每一横行从中间到两边依次递减
因此我们直接从中间对称轴倒序二分找起即可!
C(r, k)对应的顺序值为：(r + 1) * r / 2 + k + 1
二分的左右端点：l：2k，r：max(n, l)
右端点一定不能比左端点小！
特例：否则当n=1时，会出问题！
*/
// C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
LL C(int a, int b){
LL res = 1;
for(int i = a, j = 1; j <= b; i --, j ++){
res = res * i / j;
// 大于n已无意义，且防止爆LL
if(res > n) return res;
}
return res;
}
bool check(int k){
// 二分该斜行,找到大于等于该值的第一个数
// 左边界2k，右边界为max(l, n)取二者最大即可！
int l = 2 * k, 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;
// C(r, k)的从0开始的顺序！
cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;
return true;
}
int main(){
cin >> n;
// 从第16斜行枚举即可！
for(int k = 16; ; k --)
if(check(k)) break;
return 0;
}
赞
我见过的解释的最清晰的图😍😍
牛的
厉害
这不是从下到上分别二分16条斜线上的数字把，这是直接二分$C^k_{2k}$ ~ $C^k_n$，例如$C^{16}_{32}$ ~ $C^{16}_{1e9}$。直接爆
long long，但是有一个判断避免了爆long long，就是if(res > n) return res;。左边界为什么是2k
每一个斜行的第一个数就是C 2k取k，所以2k作为二分的左边界
orz，看懂左边界了，可是我不明白为什么右边界是n啊，n不是要查找的数吗，为什么还要和2k一起求mid啊，实在是想不通了orz！！！
2k和n都是行号。假如我们要找n这个数，我们一定可以在第n行的第1个数找到，也就是C（n,1），但是这个n可能不是第一个出现的n。例如杨辉三角里面的6这个数，它在（6,1）和（4,2）均出现了，要找第一个出现的6，应该是（4,2）这个。
每个斜行的起点的行号是2k,终点是n。而起点的值是C(2k,k)，终点的值是C(n,k)我们要在[2k,n]在这个区间内找到等于n的值
这里二分的是每一个斜行的组合数的底数
每一个斜行的第一个数就是C 2k取k，所以2k作为二分的左边界
而关于右边界r=n是因为当k>=1时 C n取k 肯定大于等于n
懂了懂了，非常感谢！！
中间对称轴的数是
C(2k, k)，因为我们要枚举16个斜列，然后在斜列上二分寻找>=n的最大的数字，确定这个数字需要行号，而该斜列 最小的行号 就是2k，接着就是2k+1, 2k+2, ... , n所以二分的左右边界为
[2k, n]。👍👍👍
杨辉三角形为啥是组合数呀？咋看出来的？
高中数学啊
我高中是文科😂😂
高中是文科生不用学数学吗
文科生是咋选计算机的，我挺好奇，是经济类的吗？
和理科学的数学不一样
是大数据😅
为啥 i 从 0 到 16 正序枚举结果就不对了呢？
你正着枚举在第二列直接就找到了这个数而且是错误的编号，不是第一个出现的
因为第二斜列是从2~1e9的，所以在第二斜列就能找到这个数，但不是第一个，
为什么
r = max(n, l)？找每列大于n的行数范围，以n为底的组合数肯定大于n，然后如果n < l 组合数直接设为l为底就行了，肯定不在这一列。
那万一n很大，以n为底的组合数超级大，那不就直接爆了吗？
是不是反正求组合数的函数中会直接跳掉所以没事
对，求组合数函数里面写了，超过n直接返回，防止爆long long
okok理解了
每一列大于n的行数范围是啥意思？
如果一开始n就小于l，那么r的取值等于l,不会进行二分
如果一开始n小于l，那么这一斜行第一个（最小的）元素就大于n，那这一斜行就不存在n，即全都大于n，直接二分上一斜行
因为最后他求的是C(r, k), 改成C(l, k)就不用r = max(n, l)了。
【帅！】
为啥在主函数的循环里我加一个 k > 0就出错了？？？
傻了，有第0斜行，要加也是k >= 0
最后求顺序值的时候 (r + 1) * r / 2 + k + 1 到底怎么来的呀
每一层多一个数，等差数列求和
当为C4,2 == 6时，r = 4，k = 2，它的前面有4行，前面4行的总个数为1 + 2 + 3 + 4= 10，也就是 (r + 1) * r / 2，再加上它在这行的位置k + 1
大佬，LL C(int a, int b)那一段双指针是什么意思呢？刚入算法的渣渣看不懂QAQ
求组合数的
左边界，右边界是什么意思呢？
就是斜线的右上角的行数和左下角的行数
原来1LL是为了在计算时，把int类型的变量转化为long long，然后再赋值给long long类型的变量。（学到啦！！）
我终于看懂啦！！一直搞不懂为什么16斜行能包含所有1到1e9的数，以为是前32行的数里找，现在看了代码清楚多了(^_^)
res = res * i / j; 换成 res *= i / j 有问题
可能是精度问题，还后再进行乘之前会舍弃余数
前者先乘后除 后者先除再乘
这个r=max(n,l)这里有点懵，我如果要找56的话，我输入的n=56，那r也取56了，mid不就变得很大了吗，那数据不就直接爆掉了吗？
哦是不是因为反正在后面求组合数的函数里只要大于n之后就被直接返回，就不用管过程中爆不爆的问题了
前16个斜行一定包含了1到1e9的所有数字吗
一定呀，题解写了
因为是斜着的，所以要考虑
大佬写的太好了，不明白l和r的取值是怎么来的，看完很清晰了瞬间，感谢Orz
当n == 1是会出啥问题啊，我把n == 1带入模拟代码没啥问题啊
特例：否则当n=1时，会出问题！
注：当n=1时，k从16往下检查时，当k=1时，l=2k,r=n=1,因为l>r，会直接跳出二分的while循环
C（r,k）=C（1,1）=1。根据C（1,1）得到的顺序值，此时就会输出1的位置是3，但是这个位置不是第一次出现的位置。正确的位置应该是(0,0)
这里应该不可能爆longlong吧，c(34,17)才1e15,怎么爆？？？？
求阶乘的过程中会爆的，你测试下数据1000000000的时候，然后数据比较弱，res > n的时候返回不写也能过，蓝桥杯官网过不了的。
想问下这种求组合数的方式是算法基础课模板里的第几种呢？
硬求的啊,直接循环处理阶乘
cout << 1ll * (r + 1) * r / 2 + k + 1 << endl;
这里的1ll是什么？
long long 的1