题目描述
杨辉三角
样例
略
算法1
(找规律+二分) $O(nlogn)$
首先找到组合数的关系,第十六斜行是k,那么中间的组合数为C(2K,K),杨辉三角是对称的,找到中间的数,并且二分左边的斜行。通过观察可知C(32,16)<=n,C(34,17)>n,所有答案就在斜行16及以前,对于每一斜行,二分找满足的值,因为是单调递增的,且要倒着从16开始枚举,不然找到的不是第一个。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int n;//斜行为k,组合数是C(ZK,K)
//求组合数
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.tie(0);
cout.tie(0);
cin>>n;
for(int i=16;;i--)//答案在第十六斜行以前
{
if(check(i))break;
}
return 0;
}