求解玄关
查看原帖
求解玄关
581103
liangjiaqi2021楼主2025/1/4 15:13

求解,加上19,20行的

if (ret > n)
			return ret;

就会出错,不加就AC,老师的代码也有这两行就没问题

附上我的代码:

// #include <iostream>
#include <cstdio>
// #define int long long
#define abs(x) (((x)>0)?(x):-(x))
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define isdigit(x) ((x)>='0'&&(x)<='9')
using namespace std;
typedef long long ll;
// const int N = 1145141919810; // 哼 哼 哼 啊啊啊啊啊啊啊啊
ll n;
ll combine(ll x, ll y)
{
	ll ret = 1;
	for (ll i = 0; i < y; ++i)
	{
		ret = ret * (x-i) / (i+1);
		 // 加上下面这两行就会出错 输入6 输出38 应该是13
		if (ret > n)
			return ret;
	}
	return ret;
}
ll pos(ll x, ll y)
{
	return ((x*(x-1))>>1)+y;
	// return x*(x-1)/2+y+1;
}
void solve()
{
	ll n;
	scanf("%lld", &n);
	if (n == 1)
	{
		printf("1\n");
		return;
	}
	for (ll i = 16; i; --i)
	{
		ll l = 2, r = 1e9;
		while (l <= r)
		{
			// ll mid = (l+r) / 2;
			ll mid = (l+r) >> 1;
			ll res = combine(mid, i);
			if (res == n)
			{
				// cout << (mid+1)*mid/2+i+1;
				// printf("%lld\n", (mid+1)*mid/2+i+1);
				printf("%lld\n", pos(mid+1, i+1));
				return;
			}
			if (res < n)
				l = mid + 1;
			else
				r = mid - 1;
		}
	}
}
signed main()
{
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	// ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // iostream加速
	solve();
	return 0;
}
2025/1/4 15:13
加载中...