思路分析
代码实现
做法一:性质法
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL n, k, M, D;
int main()
{
cin >> n >> k >> M >> D;
LL res = 0;
for(int d = 1; d <= D; d ++)
{
LL y = (d - 1) * k + 1;
//如果想防止y爆long long,可以定义为__int128
if(y > n) break; // 当y大于n的时候,n/x是不可能大于y的,因为x是大于1的数,n/x一定小于n
LL x = min(M, n / y); // x最大值只能取M
if(n / x >= y && n / x <= d * k)
res = max(res, d * x);
}
cout << res << endl;
return 0;
}
做法二:二分
#include <iostream>
using namespace std;
using LL = long long;
int main() {
LL n, k, M, D;
cin >> n >> k >> M >> D;
LL res = 0;
for (int d = 1; d <= D && (d - 1) * k + 1 <= n; d++)
{
LL l = 0, r = M + 1;
while (l + 1 < r) {
LL mid = l + r >> 1;
if (n / mid >= (d - 1) * k + 1) l = mid;
else r = mid;
}
if (n / l <= d * k) res = max(res, d * l);
}
cout << res << endl;
return 0;
}