P13604 [NWRRC 2022] Greatest Common Divisor

Gennady 是一名有志成为程序员的人。他目前正在学习用于计算两个正整数最大公约数的欧几里得算法。 不幸的是，Gennady 有时会混淆整数除法运算符（记作 $\tt{div}$）和取余运算符（记作 $\tt{mod}$）。例如，$37$ $\tt{div}$ $10 = 3$，而 $37$ $\tt{mod}$ $10 = 7$。 以下是 Gennady 最新实现的欧几里得算法： - 输入：两个正整数 $x$ 和 $y$。 - 当 $y > 0$ 时： - 令 $x = x$ $\tt{div}$ $y$，然后交换 $x$ 和 $y$。 - 输出 $x$。 如你所见，如果 Gennady 用的是 $\tt{mod}$ 运算符而不是 $\tt{div}$ 运算符，他的实现就是正确的：上述算法能够成功求出 $x$ 和 $y$ 的最大公约数。然而，事实证明，即使有这个严重的 bug，这个算法有时也能给出正确的结果！ 现在给定一个整数 $n$。Gennady 想要找出所有满足 $1 \le x, y \le n$，该算法能够终止并输出正确结果的输入对 $(x, y)$。设这些输入对按字典序排列为 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$（对于所有 $1 \le i < k$，要么 $x_i < x_{i+1}$，要么 $x_i = x_{i+1}$ 且 $y_i < y_{i+1}$）。 你还会得到 $q$ 个询问。第 $i$ 个询问是一个正整数 $p_i$，你需要输出 $x_{p_i}$ 和 $y_{p_i}$，或者报告 $p_i > k$。

第一行包含两个整数 $n$ 和 $q$，分别表示输入值的上界和询问的数量（$1 \le n, q \le 2 \cdot 10^5$）。 接下来的 $q$ 行，每行包含一个整数 $p_i$（$1 \le p_i \le n^2$）。

对于每个询问，输出两个整数。它们要么是 $x_{p_i}$ 和 $y_{p_i}$，表示按字典序排列的第 $p_i$ 个满足条件的输入对，要么输出 $-1\ -1$，如果这样的输入对数量少于 $p_i$。

由 ChatGPT 4.1 翻译