codeforces-scrape

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

1826B.md (1645B)


      1 Source: https://codeforces.com/problemset/problem/1826/B
      2 
      3 B. Lunatic Never Content
      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 You have an array $a$ of $n$ non-negative integers. Let's define $f(a, x) = [a_1 \bmod x, a_2 \bmod x, \dots, a_n \bmod x]$ for some positive integer $x$. Find the biggest $x$, such that $f(a, x)$ is a palindrome.
     22 
     23 Here, $a \bmod x$ is the remainder of the integer division of $a$ by $x$.
     24 
     25 An array is a palindrome if it reads the same backward as forward. More formally, an array $a$ of length $n$ is a palindrome if for every $i$ ($1 \leq i \leq n$) $a_i = a_{n - i + 1}$.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$).
     32 
     33 The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 10^9$).
     34 
     35 It's guaranteed that the sum of all $n$ does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case output the biggest $x$, such that $f(a, x)$ is a palindrome. If $x$ can be infinitely large, output $0$ instead.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 2
     49 
     50 1 2
     51 
     52 8
     53 
     54 3 0 1 2 0 3 2 1
     55 
     56 1
     57 
     58 0
     59 
     60 3
     61 
     62 100 1 1000000000
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 1
     69 2
     70 0
     71 999999900
     72 ```
     73 
     74 Note
     75 
     76 In the first example, $f(a, x = 1) = [0, 0]$ which is a palindrome.
     77 
     78 In the second example, $f(a, x = 2) = [1, 0, 1, 0, 0, 1, 0, 1]$ which is a palindrome.
     79 
     80 It can be proven that in the first two examples, no larger $x$ satisfies the condition.
     81 
     82 In the third example, $f(a, x) = [0]$ for any $x$, so we can choose it infinitely large, so the answer is $0$.