CF1766D Lucky Chains

我们称一对正整数 $(x, y)$ 为幸运对，如果它们的最大公约数等于 $1$（即 $\gcd(x, y) = 1$）。 我们定义由 $(x, y)$ 引出的链为一系列对：$(x, y)$，$(x + 1, y + 1)$，$(x + 2, y + 2)$，$\dots$，$(x + k, y + k)$，其中 $k \ge 0$。链的长度为其包含的对的数量，即 $(k + 1)$。 如果链中的所有对都是幸运对，则称该链为幸运链。 给定 $n$ 个对 $(x_i, y_i)$。对于每一对，计算由该对引出的最长幸运链的长度。注意，如果 $(x_i, y_i)$ 本身不是幸运对，则链的长度为 $0$。

第一行包含一个整数 $n$（$1 \le n \le 10^6$），表示对的数量。 接下来的 $n$ 行，每行包含一对整数 $x_i$ 和 $y_i$（$1 \le x_i < y_i \le 10^7$），表示对应的对。

输出 $n$ 个整数，第 $i$ 个整数表示由 $(x_i, y_i)$ 引出的最长幸运链的长度。如果该链可以无限长，则输出 $-1$。

在第一个测试用例中，$\gcd(5, 15) = 5 > 1$，所以它本身就不是幸运对，因此幸运链的长度为 $0$。 在第二个测试用例中，$\gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2$。因此，幸运链只包含单个对 $(13, 37)$。 由 ChatGPT 4.1 翻译