1457.杨辉三角形

题目描述

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,⋯
给定一个正整数 N，请你输出数列中第一次出现 N 是在第几个数？

输入描述

输入一个整数 N。

输出描述

输出一个整数代表答案。

输入输出样例

示例 1
输入

6

输出

13

评测用例规模与约定

对于 20​​ 的评测用例，1≤N≤10​； 对于所有评测用例，1≤N≤1000000000。

运行限制

最大运行时间：1s
最大运行内存: 256M

#include <iostream>
#include <cmath>
using namespace std;

long long N;

long long C(int a, int b) {
  long long res = 1;
  for (long long i = a, j = 1; j <= b; i--, j++) {
    res = res * i / j;
    if (res > N) {
      return res;
    }
  }
  return res;
}

int main()
{
  // 请在此输入您的代码
  cin >> N;
  for (long long i = 16; i >= 0; i--) {
    long long l = 2 * i, r = max(i,N), mid;
    while (l <= r) {
      mid = (r - l) / 2 + l;
      if (C(mid, i) == N)  break;
      else if (C(mid, i) < N) l = mid + 1;
      else r = mid - 1;
    }
    if (C(mid, i) == N) {
      cout << (1 + mid) * mid / 2 + i + 1;
      break;
    }
  }
  return 0;
}