[Solution] Three Days Grace Codeforces Solution

E. Three Days Grace

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Ibti was thinking about a good title for this problem that would fit the round theme (numerus ternarium). He immediately thought about the third derivative, but that was pretty lame so he decided to include the best band in the world — Three Days Grace.

You are given a multiset A$A$ with initial size n$n$, whose elements are integers between 1$1$ and m$m$. In one operation, do the following:

• select a value x$x$ from the multiset A$A$, then
• select two integers p$p$ and q$q$ such that p,q>1$p,q>1$ and p⋅q=x$p\cdot q=x$. Insert p$p$ and q$q$ to A$A$, delete x$x$ from A$A$.

Note that the size of the multiset A$A$ increases by 1$1$ after each operation.

We define the balance of the multiset A$A$ as max(ai)−min(ai)$max(a_i)-min(a_i)$. Find the minimum possible balance after

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 performing any number (possible zero) of operations.

Input

The first line of the input contains a single integer t$t$ (1≤t≤105$1\le t\le {10}^5$) — the number of test cases.

The Third Three Number Problem Codeforces Solution

Almost Ternary Matrix Codeforces Solution

The Third Problem Codeforces Solution

Almost Triple Deletions CodeForces Solution

Three Days Grace Codeforces Solution

The second line of each test case contains two integers n$n$ and m$m$ (1≤n≤106$1\le n\le {10}^6$, 1≤m≤5⋅106$1\le m\le 5\cdot {10}^6$) — the initial size of the multiset, and the maximum value of an element.

The third line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤m$1\le a_i\le m$) — the elements in the initial multiset.

It is guaranteed that the sum of n$n$ across all test cases does not exceed 106${10}^6$ and the sum of m$m$ across all test cases does not exceed 5⋅106$5\cdot {10}^6$.