# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Pratik Kumar

Tester: Nishank Suresh, Utkarsh Gupta

Editorialist: Pratiyush Mishra

# DIFFICULTY:

2671

# PREREQUISITES:

None

# PROBLEM:

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

- B_i \ge 0 for each 1 \leq i \leq N
- The GCD of adjacent elements of B is equal to 1, i.e, \gcd(B_i, B_{i+1}) = 1 for each 1 \leq i \lt 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+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 + 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 + 7 (which is 0 \pmod {10^9 + 7}). The output in this case would be 500 and not 0.

# EXPLANATION:

**Observation 1:** Let us take k as the max(|A_i - B_i|), \; 1 \leq i \leq N. We would note that k is small(less than 20).

Now using the above observation let us solve this problem using DP.

Let us define our dp dp[i][j], where 1 \leq i \leq n and -k \leq j \leq k.

Here dp[i][j] stores the minimum cost and denotes that we have processed till i_{th} index and the element at the i_{th} index is modified to (A[i] + j). Now let us compute dp[i][j].

Clearly dp[i][j] depends on dp[i-1][j'], \;where \; -k \leq j' \leq k. As we are computing dp[i][j], we know that the value of i_{th} index is A[i] + j, so dp[i][j] depends on dp[i-1][j'] if and only if gcd(A[i] + j,A[i-1] + j') is 1. In that case:

So we compute this dp and our answer would be min(dp[n][j]), where\; -k \leq j \leq k

# TIME COMPLEXITY:

O(Nk^2), for each test case.