Topics : Seive, dynamic Programming, segment tree.
First, we need to find a naive solution. Then we will optimize it to fit inside our time limit. Let's say we have computed ans for first i-1 elements. Now what will be the cost if previous subarray is finished at jth (1<=j<=i-1 and gcd (aj+1, aj+2,.........,ai)>1) index. We have to minimize this value. In short we have to do something like this
for i from 1 to n
g=a[i]
for j from i-1 to 1 and g>1
dp[i]=min(dp[i], dp[j]+cost(j+1 to i)
g=gcd(g, a[j])
But this solution is too slow. It can be optimized using segment tree (or anything that can do range update and range query efficiently). When we are at ith index, then jth(1 <= j< i) index of segment tree will store value of dp[j]+cost(j+1 to i). Notice, ith index will only contribute to till previous index where ai occurred. In another word we will add ai to all the index till previous position of ai. Now dp[i] will be minimum from last j where gcd(aj+1, aj+2, ..........., ai-1)>1 to i-1.
To find this last j. We need to maintain an array Pre[1....10^6] which will contain number of consecutive index a prime divisor of ai occurred. If x is a prime divisor of ai then we will increase Pre[x] by 1. And if y is a prime divisor ai-1 but does not divide ai then we will set Pre[y] to zero. Then j=i-Max(Pre[1],Pre[2],.....Pre[10^6]).
