神仙题.jpg

首先答案满足可二分性，二分后变成了判定性问题。

我们想想现在有个 \(n \times mid\) 的表格，初始时全为 \(0\)，每次我们能将一列中 \(m\) 个数添上 \(1\)，要求最后每一行都不能一样。

现在我们换一种角度，我们考虑一行一行的填，依然要满足上面那两个条件。

最优的操作是我们先一行只有 \(1\) 个 \(1\) 的填，然后一行 \(2\) 个 \(1\) ...

对于一行有 \(i\) 个 \(1\) 的情况,一共会有 \(C_{mid}^i\) 行，每列会多 \(C_{mid}^{i-1}\) 个 \(1\) ,这里的组合数是可以递推的。

如果行不够了，看列方面能不能撑得住，最多的一列会多 \(\displaystyle \left \lceil \frac{res1 \times i}{mid}\right \rceil\),看是否 \(\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 << '\n';
	}
	return 0;
}