神仙题.jpg
首先答案满足可二分性，二分后变成了判定性问题。
我们想想现在有个 (n imes mid) 的表格，初始时全为 (0)，每次我们能将一列中 (m) 个数添上 (1)，要求最后每一行都不能一样。
现在我们换一种角度，我们考虑一行一行的填，依然要满足上面那两个条件。
最优的操作是我们先一行只有 (1) 个 (1) 的填，然后一行 (2) 个 (1) ...
对于一行有 (i) 个 (1) 的情况,一共会有 (C_{mid}^i) 行，每列会多 (C_{mid}^{i-1}) 个 (1) ,这里的组合数是可以递推的。
如果行不够了，看列方面能不能撑得住，最多的一列会多 (displaystyle left lceil frac{res1 imes i}{mid} ight ceil),看是否 (le res2)
否则如果列不够了，就一票否决了。
最后看是否有空行
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int T, n, m, ans, l, r, mid;
inline int read()
{
int res = 0; char ch = getchar(); bool XX = false;
for (; !isdigit(ch); ch = getchar())(ch == '-') && (XX = true);
for (; isdigit(ch); ch = getchar())res = (res << 3) + (res << 1) + (ch ^ 48);
return XX ? -res : res;
}
int check(int mid)
{
int C1 = mid, C2 = 1, res1 = n - 1, res2 = m;
for (int i = 1; i <= mid; ++i)
{
if (i > 1)
{
C1 = C1 * (mid - i + 1) / i;
C2 = C2 * (mid - i + 1) / (i - 1);
}
if (res1 < C1)return (res1 * i + mid - 1) / mid <= res2;
else if (res2 < C2)return 0;
res1 -= C1; res2 -= C2;
}
return !res1;
}
signed main()
{
cin >> T;
while (T--)
{
n = read(); m = read();
l = 0; r = n - 1;
while (l <= r)
{
mid = (l + r) >> 1;
if (check(mid))ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << '
';
}
return 0;
}