蓝桥杯2021年第十二届省赛真题-杨辉三角形

1.杨辉三角可以用组合数表示

2.杨辉三角是对称的，可以只看前半部分

3.将三角形斜过来观察，从下往上搜索

#include <iostream>

#include <cstring>

#include <algorithm>

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;

if (res > n)

return res;

}

return res;

}

bool check(int k) {

LL l = k * 2, r = max((LL)n, l);

while (l < r) {

LL mid = l + r >> 1;

if (C(mid, k) >= n)

r = mid;

else

l = mid + 1;

}

if (C(r, k) != n)

return false;

cout << r * (r + 1) / 2 + k + 1 << endl;

return true;

}

int main() {

cin >> n;

for (int k = 16; ; k -- )

if (check(k))

break;

return 0;

}