AcWing 3418. 杨辉三角形
原题链接
中等
作者:
最后五分钟
,
2024-04-08 22:56:30
,
所有人可见
,
阅读 4
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=10010,M=10010;
typedef pair<int,int> PII;
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-1,r=max(2*k,n)+1;
while(l+1!=r)
{
int mid=l+r>>1;
if(c(mid,k)>=n)r=mid;
else l=mid;
}
if(c(r,k)!=n)return 0;
int ans=r*(r+1)/2+k+1;
cout<<ans<<endl;
return 1;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int k=16;;k--)
if(check(k))break;
return 0;
}