4022209_ac_1110ms_204k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 58 行

#include <stdio.h>

__int64 fmax(__int64 a, __int64 b)
{
	return a > b ? a : b;
}

__int64 fmin(__int64 a, __int64 b)
{
	return a < b ? a : b;
}

//i ^ 2 + 100000 * i + j ^ 2 - 100000 * j + i * j

int main()
{
	int cas;
	__int64 b, c;
	__int64 n, m, j, cnt;
	__int64 max, min, mid;

	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%I64d%I64d", &n, &m);
		max = fmax(n * n + 100001 * n - 99999, 3 * n * n);
		min = fmin(3, n * n + 100001 - 100000 * n + n);
		while (min < max)
		{
			mid = (min + max) >> 1;
			cnt = 0;
			for (j = 1; cnt < m && j <= n; j++)
			{
				b = 100000 + j;
				c = j * (j - 100000);
				__int64 mmin, mmax, mmid;
				mmin = 1;mmax = n + 1;
				while (mmin < mmax)
				{
					mmid = (mmin + mmax) >> 1;
					__int64 tmp = mmid;
					__int64 v = tmp * tmp + b * tmp + c;
					if (v > mid)
						mmax = mmid;
					else
						mmin = mmid + 1;
				}
				cnt += mmin - 1;
			}
			if (cnt >= m)
				max = mid;
			else
				min = mid + 1;
		}
		printf("%I64d\n", min);
	}
	return 0;
}