no of ways of having an A array of length N formed using only [1,2,…M] 1<=M<=10 with condition that gcd(A[i],A[i+1]) 1
Input N M
Constraints 1<=N<=1e10 1<=M<=10
Test Case1: 1 1
Output: 1
Explanation: { [1] }
Test Case2: 2 2
Output : 3
Explanation: { [1, 1] , [1, 2] , [2 , 1]}
I am not able to understand the question. 
more formally the question is asking for number of arrays of length n with consecutive digits as coprime using elements of array belonging to range [1,M] given n amd m find ans%k;
k=1e9+7;
Thanks for explaining the problem.
Maybe we can try this approach.
DP[i][j] = # number of ways such that the length of array is i now and the element at position i is j.
We can fill this DP array such that going form i to i+1 we need to find for each chosen j the number of coprimes to it and add those.
That is
DP[i][j] = \sum_{k=1}^{m} DP[i-1][k] such that gcd(j,k) = 1
Final answer \sum_{k=1}^{m} DP[n-1][k]
Don’t forget the modulo.
1 Like
N is huge(N = 1e10)?
I think there is something combinotorics with dp.
As m is small (10) we can think like filling the subsets in the array.May be…
1 Like
I did not notice the constraints.
I think we can use fast matrix exponentiation to do this in log(n) .
The matrix is m * m and matrix[i][j] = 1 if gcd(i,j) = 1 else 0.