1766D.md (1602B)
1 Source: https://codeforces.com/problemset/problem/1766/D 2 3 D. Lucky Chains 4 5 time limit per test 6 7 4 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$). 22 23 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)$. 24 25 Let's name such chain lucky if all pairs in the chain are lucky. 26 27 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$. 28 29 Input 30 31 The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the number of pairs. 32 33 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 \lt y_i \le 10^7$) — the corresponding pair. 34 35 Output 36 37 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. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 5 15 46 13 37 47 8 9 48 10009 20000 49 ``` 50 51 Output 52 53 ``` 54 0 55 1 56 -1 57 79 58 ``` 59 60 Note 61 62 In the first test case, $\gcd(5, 15) = 5 \gt 1$, so it's already not lucky, so the length of the lucky chain is $0$. 63 64 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)$.