求解,加上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;
}