Explain how to solve the problem Vanya and GCD Array | Practice Problems
I am going to assume you are already familiar with dynamic programming. Here is the explanation.
We are given an array A of length N. Let’s work with a function f(i, g) which returns the number of increasing subsequences that end at index i (and begin at any index before that) which have gcd=g. We will compute this function for all relevant values of i and g, and at the end our answer will be \sum\limits_{i=1}^{n}f(i,1).
How do we recursively define our function f(i, g)?
Let there be some increasing subsequence S that ends at index j < i. We can only append A[i] to the end of S if A[j] < A[i], because we only want increasing subsequences. Let’s say this condition is satisfied, then S concatenated with A[i] will be an increasing subsequence that ends at index i with gcd value equal to gcd(gcd(S), A[i]).
Hence, the number of increasing subsequences that end at i with gcd=g will be the total number of increasing subsequences that end at some j < i such that A[i]>A[j] and the gcd of these subsequences and A[i] equal g.
The base case arises for each subsequence of length 1, i.e. the a single element of A. For g=A[i], the value of f(i, g) is the above summation plus 1, for the single element itself is an increasing subsequence.
As the maximum value of A[i] is 100, the dp table will be required of dimension N \times 100, and time complexity will be \mathcal{O}(N^2 \times 100). Take a look at the pseudocode below
for i in [1..n]
for g in [1..100]
dp[i][g] = 0
dp[i][a[i]] = 1
for j in [1..i-1]
if a[i]<=a[j]
continue
for k in [1..a[j]]
g = gcd(a[i], k)
dp[i][g] += dp[j][k]
Of course we need to perform the modulo operation at every step, and calculate the answer at the end and print it. My code is here if you need it.
Hope this helps 
4 Likes