codeforces-scrape

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

1708B.md (1523B)


      1 Source: https://codeforces.com/problemset/problem/1708/B
      2 
      3 B. Difference of GCDs
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given three integers $n$, $l$, and $r$. You need to construct an array $a_1,a_2,\dots,a_n$ ($l\le a_i\le r$) such that $\gcd(i,a_i)$ are all distinct or report there's no solution.
     22 
     23 Here $\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$.
     24 
     25 Input
     26 
     27 The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.
     28 
     29 The first line contains three integers $n$, $l$, $r$ ($1 \le n \le 10^5$, $1\le l\le r\le 10^9$).
     30 
     31 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     32 
     33 Output
     34 
     35 For each test case, if there is no solution, print "NO" (without quotes). You can print letters in any case (upper or lower).
     36 
     37 Otherwise, print "YES" (without quotes). In the next line, print $n$ integers $a_1,a_2,\ldots,a_n$ — the array you construct.
     38 
     39 If there are multiple solutions, you may output any.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 5 1 5
     48 9 1000 2000
     49 10 30 35
     50 1 1000000000 1000000000
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 YES
     57 1 2 3 4 5
     58 YES
     59 1145 1926 1440 1220 1230 1350 1001 1000 1233
     60 NO
     61 YES
     62 1000000000
     63 ```
     64 
     65 Note
     66 
     67 In the first test case, $\gcd(1,a_1),\gcd(2,a_2),\ldots,\gcd(5,a_5)$ are equal to $1$, $2$, $3$, $4$, $5$, respectively.