codeforces-scrape

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

2179C.md (1513B)


      1 Source: https://codeforces.com/problemset/problem/2179/C
      2 
      3 C. Blackslex and Number Theory
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Blackslex worked too hard and started dreaming about numbers. Solve the following task from his dreams.
     22 
     23 You are given an array $a_1, a_2, \ldots, a_n$.
     24 
     25 In one operation you choose an index $i$ ($1 \le i \le n$) and an integer $x$ which is at least $k$ and set $$ a_i := a_i \bmod x, $$ where $u \bmod v$ denotes the remainder of dividing $u$ by $v$.
     26 
     27 Your goal is to make all elements of the array identical. Among all positive integers $k$, determine the maximum $k$ for which there exists a finite sequence of the above operations that makes all array elements equal.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$).
     34 
     35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$, all values of $a$ are distinct).
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, print a single integer — the maximum positive integer $k$ such that it is possible to make all elements of the array identical using any number of operations with moduli $x$ restricted to $k \le x$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 3
     51 
     52 5 7 9
     53 
     54 2
     55 
     56 2 3
     57 
     58 7
     59 
     60 11 74 5 22 52 97 82
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 5
     67 
     68 2
     69 
     70 6
     71 ```