【题目描述】
下面的图形为著名的杨辉三角形
如果我们按从上到下，从左到右的顺序把所有数排成一列，可以得到如下数列：
1 , 1 , 1 , 1 , 2 , 1 , 1 , 3 , 3 , 1 , 1 , 4 , 6 , 4 , 6 , 1...... 1,1,1,1,2,1,1,3,3,1,1,4,6,4,6,1......1,1,1,1,2,1,1,3,3,1,1,4,6,4,6,1......
给定一个正整数N，求出N第一次出现是在第几个数？
1 < = N < = 109
【输入】
数字n
【输出】
N第一次出现的位置（从1开始计算）
【样例输入】
6
【样例输出】
13
【参考代码】
#include<algorithm> #include<iostream> typedef long long ll; using namespace std; int N; ll combine(int n, int m) { ll ans = 1; for (int i = 0; i < m; i++) { ans *= (n - i); ans /= (i + 1); if (ans > N) { return ans; } } return ans; } bool f(int k) { int l = 2 * k, r = max(N, l); while (l < r) { int mid = (l + r) >> 1; if (combine(mid, k) >= N) { r = mid; } else { l = mid + 1; } } if (combine(r, k) == N) { cout << 1ll * (r + 1) * r / 2 + k + 1 << endl; return true; } else { return false; } } int main() { cin >> N; if (N == 1) { cout << "1" << endl; } else { for (int i = 17; i > 0; i--) { if (f(i)) { break; } } } return 0; }
