codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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)$.