题目描述

输入输出

运行结果

样例点全部通过
在这里插入图片描述

代码

#include<iostream>
using namespace std;
const int N = 1e6+5;

typedef long long LL;

LL f[30]={1,1};
LL n;
bool check(LL x,int k){
	LL temp=1;
	for(int i=0;i<k;++i){
		if(temp>n*f[k])return 0;
		temp*=(x+i);
	}
	return temp<=n*f[k];
}
int main(){
	for(int i=2;i<21;++i)f[i]=f[i-1]*i;
	scanf("%lld",&n);
	if(n==1){
		printf("1\n");
		return 0;
	}
	LL ans=(n+1)*n/2+2;
	for(int i=2;i<20;++i){
		LL l=i,r=n,res=-1;
		while(l<=r){
			LL mid=(l+r)>>1;
			if(check(mid,i)){
				l=mid+1;
				res=mid;
			}else r=mid-1;
		}
		LL temp=1;
		for(int j=0;j<i;++j){
			temp*=(res+j);
		}
		if(temp==f[i]*n){
			ans=min(ans,(res+i-1)*(res+i)/2+i+1);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

分析

杨慧三角上的任意一个数皆可以写成组合数C(n,m) (n为下标，m为上标)，且C(n,m)对应杨慧三角的第n+1行，第m+1列，对应第 $m + 1 + n ? (n + 1) / 2$ 个数。
因为C(N，1)=N，所以，当输入N时，解ans最大不超过N*(N+1)/2 + 2。如果还存在C(n,m)=N，则可以更新ans。可知，要更新ans，n必定小于N。假设C(n,m)=N是最终答案，则此时n*(n-1)…(n-m+1)=N*m! 且m<=(n+1)/2。因为N范围小于等于1e9，所以估算可得m不大于20（实际测试时m小于10也可以过）。故可以从1到20枚举m，此时上方等式的右半部分已定，所以可以二分找到n，有了n和m就可以知道在第几位了。