codeforces-scrape

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

1909B.md (2691B)


      1 Source: https://codeforces.com/problemset/problem/1909/B
      2 
      3 B. Make Almost Equal With Mod
      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 [xi - Solar Storm](https://soundcloud.com/yugenero/xi-solar-storm)
     22 
     23 ⠀
     24 
     25 You are given an array $a_1, a_2, \dots, a_n$ of distinct positive integers. You have to do the following operation exactly once:
     26 
     27 * choose a positive integer $k$;
     28 * for each $i$ from $1$ to $n$, replace $a_i$ with $a_i \text{ mod } k^\dagger$.
     29 
     30 Find a value of $k$ such that $1 \leq k \leq 10^{18}$ and the array $a_1, a_2, \dots, a_n$ contains exactly $2$ distinct values at the end of the operation. It can be shown that, under the constraints of the problem, at least one such $k$ always exists. If there are multiple solutions, you can print any of them.
     31 
     32 $^\dagger$ $a \text{ mod } b$ denotes the remainder after dividing $a$ by $b$. For example:
     33 
     34 * $7 \text{ mod } 3=1$ since $7 = 3 \cdot 2 + 1$
     35 * $15 \text{ mod } 4=3$ since $15 = 4 \cdot 3 + 3$
     36 * $21 \text{ mod } 1=0$ since $21 = 21 \cdot 1 + 0$
     37 
     38 Input
     39 
     40 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.
     41 
     42 The first line of each test case contains a single integer $n$ ($2 \le n \le 100$) — the length of the array $a$.
     43 
     44 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{17}$) — the initial state of the array. It is guaranteed that all the $a_i$ are distinct.
     45 
     46 Note that there are no constraints on the sum of $n$ over all test cases.
     47 
     48 Output
     49 
     50 For each test case, output a single integer: a value of $k$ ($1 \leq k \leq 10^{18}$) such that the array $a_1, a_2, \dots, a_n$ contains exactly $2$ distinct values at the end of the operation.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 5
     58 
     59 4
     60 
     61 8 15 22 30
     62 
     63 5
     64 
     65 60 90 98 120 308
     66 
     67 6
     68 
     69 328 769 541 986 215 734
     70 
     71 5
     72 
     73 1000 2000 7000 11000 16000
     74 
     75 2
     76 
     77 2 1
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 7
     84 30
     85 3
     86 5000
     87 1000000000000000000
     88 ```
     89 
     90 Note
     91 
     92 In the first test case, you can choose $k = 7$. The array becomes $[8 \text{ mod } 7, 15 \text{ mod } 7, 22 \text{ mod } 7, 30 \text{ mod } 7] = [1, 1, 1, 2]$, which contains exactly $2$ distinct values ($\{1, 2\}$).
     93 
     94 In the second test case, you can choose $k = 30$. The array becomes $[0, 0, 8, 0, 8]$, which contains exactly $2$ distinct values ($\{0, 8\}$). Note that choosing $k = 10$ would also be a valid solution.
     95 
     96 In the last test case, you can choose $k = 10^{18}$. The array becomes $[2, 1]$, which contains exactly $2$ distinct values ($\{1, 2\}$). Note that choosing $k = 10^{18} + 1$ would not be valid, because $1 \leq k \leq 10^{18}$ must be true.