Lucky Chains

题意翻译

- 给出两个正整数 $(x,y)$，满足 $(x,y),(x+1,y+1),(x+2,y+2),\dots,(x+k,y+k)$ 都是互质的，直到 $(x+k+1,y+k+1)$ 起不互质 - 问 $k$ 的值，或指出这个互质的序列长度为 $0$ 或是无限长的 翻译提供者：https://www.luogu.com.cn/user/36285

题目描述

Let's name a pair of positive integers $ (x, y) $ lucky if the greatest common divisor of them is equal to $ 1 $ ( $ \gcd(x, y) = 1 $ ). Let's define a chain induced by $ (x, y) $ as a sequence of pairs $ (x, y) $ , $ (x + 1, y + 1) $ , $ (x + 2, y + 2) $ , $ \dots $ , $ (x + k, y + k) $ for some integer $ k \ge 0 $ . The length of the chain is the number of pairs it consists of, or $ (k + 1) $ . Let's name such chain lucky if all pairs in the chain are lucky. You are given $ n $ pairs $ (x_i, y_i) $ . Calculate for each pair the length of the longest lucky chain induced by this pair. Note that if $ (x_i, y_i) $ is not lucky itself, the chain will have the length $ 0 $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 10^6 $ ) — the number of pairs. Next $ n $ lines contains $ n $ pairs — one per line. The $ i $ -th line contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i < y_i \le 10^7 $ ) — the corresponding pair.

输出格式

Print $ n $ integers, where the $ i $ -th integer is the length of the longest lucky chain induced by $ (x_i, y_i) $ or $ -1 $ if the chain can be infinitely long.

输入输出样例

输入样例 #1

4
5 15
13 37
8 9
10009 20000

输出样例 #1

0
1
-1
79

说明

In the first test case, $ \gcd(5, 15) = 5 > 1 $ , so it's already not lucky, so the length of the lucky chain is $ 0 $ . In the second test case, $ \gcd(13 + 1, 37 + 1) = \gcd(14, 38) = 2 $ . So, the lucky chain consists of the single pair $ (13, 37) $ .

**题目大意：**
幸运链问题要求我们找到由一个整数对 $(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$。**题目大意：** 幸运链问题要求我们找到由一个整数对 $(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$。