[Solution] Beautiful Array solution codechef

Beautiful Array solution codechef – You’re given an array $A$ of $N$ integers. You need to find the minimum cost of creating another array $B$ of $N$ integers with the following properties

[Solution] Beautiful Array solution codechef

• B_i \ge 0Bi​≥0 for each $1\le i\le N$
• The GCD of adjacent elements of $B$ is equal to $1$, i.e, \gcd(B_i, B_{i+1}) = 1gcd(Bi​,Bi+1​)=1 for each $1\le i<N$

The cost of creating $B$ is defined as follows:

Find the minimum possible cost to create the array $B$. Since the answer can be huge print it modulo 10^9+7109+7

Note: You need to minimize the value of total cost of creating the array $B$, and then print this minimum value modulo 10^9 + 7109+7. For example, suppose there is a way to create the required $B$ with a cost of $500$, and another way to do it with a cost of 10^9 + 7109+7 (which is 0 \pmod {10^9 + 7}0(mod109+7)). The output in this case would be $500$ and not $0$.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• The first line of each test case contains an integer $N$ – the length of the array $A$
• The second line of each test case contains $N$ space-separated integers A_1,A_2,\ldots,A_NA1​,A2​,…,AN​

Output Format

For each test case, output on a new line the minimum cost of creating the array $B$, modulo 10^9 + 7109+7.

Beautiful Array solution codechef

Sample 1:

3
3
15 16 19
2
5 10
7
9 15 7 19 10 7 1

3
3
8

Beautiful Array solution codechef Explanation

Test case $1$: The given input already satisfies all the conditions, hence we can take $B=A$ with a cost of 2^0 + 2^0 + 2^0 = 320+20+20=3.

Test case $2$: One optimal way is to choose $B$ as $[5,11]$, with a cost of 2^0 + 2^1 = 320+21=3.

For Solution

“Click Here