CF938C Constructing Tests

我们称一个 $m$-自由矩阵为一个二进制矩阵（即仅由 $1$ 和 $0$ 组成的矩阵），满足该矩阵的任意一个大小为 $m \times m$ 的正方形子矩阵中至少包含一个 $0$。 请考虑如下问题： 给定两个整数 $n$ 和 $m$，你需要构造一个大小为 $n \times n$ 的 $m$-自由矩阵，使得该矩阵中 $1$ 的数量尽可能多。请输出在这样的矩阵中，最多可以有多少个 $1$。 你不需要解决这个问题。相反，你需要为这个问题构造若干组测试数据。 你将会得到 $t$ 个数字 $x_1, x_2, \ldots, x_t$。对于每个 $x_i$，请找到两个整数 $n_i$ 和 $m_i$（$n_i \geq m_i$），使得当 $n = n_i$ 且 $m = m_i$ 时，上述问题的答案恰好等于 $x_i$。

第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示你需要构造的测试数据组数。 接下来 $t$ 行，每行包含一个整数 $x_i$（$0 \leq x_i \leq 10^9$）。 注意，在 hack 数据中必须设置 $t=1$。

对于每组测试数据，输出两个正整数 $n_i$ 和 $m_i$（$1 \leq m_i \leq n_i \leq 10^9$），使得在一个 $m_i$-自由的 $n_i \times n_i$ 矩阵中，最多可以有 $x_i$ 个 $1$。如果存在多组解，你可以输出任意一组；如果无法构造出这样的测试数据，则输出一个整数 $-1$。

由 ChatGPT 4.1 翻译