[蓝桥杯 2021 省 B] 杨辉三角形
题目描述
下面的图形是著名的杨辉三角形:
如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:
1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 1 , … 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1, \ldots 1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,…
给定一个正整数 N N N,请你输出数列中第一次出现 N N N 是在第几个数。
输入格式
输入一个整数 N N N 。
输出格式
输出一个整数代表答案。
样例 #1
样例输入 #1
6
样例输出 #1
13
提示
对于 20 % 20 \% 20% 的评测用例, 1 ≤ N ≤ 10 1 \leq N \leq 10 1≤N≤10;
对于所有评测用例, 1 ≤ N ≤ 1 0 9 1 \leq N \leq 10^9 1≤N≤109 。
蓝桥杯 2021 第一轮省赛 B 组 H 题。
杨辉三角性质
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
int n;
int C(int a, int b){
int 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){
int l = 2 * k, r = n;
if (l > r) return false;
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;
printf("%lld\n", r * (r + 1ll) / 2 + k + 1ll);
return true;
}
signed main()
{
scanf("%lld", &n);
for (int i = 16; ; i --){
if (check(i)) {
break;
}
}
return 0;
}