can u explain how to solve it

Bro I uses different test cases.

Yes, will try my test in the next contest.

Thanks for the suggestion buddy.

Its a simple dynamic programming problem

Step1:- Precompute all prime factors of number at ith index in an adjacentcy list

Step2:- Apply Top down Dp approach same as you apply for finding paths reaching nth step using recursion +dp

Step3 go for every prime factor in both the directions and update the dp[i][j],

where dp[i][j]=true if and only if you reached i in exactly j steps.

MY Simple solution can describe more.

Solution

Thanks for explanation but I see many solution using matrix exponentiation.

Any idea?

My solution was of pure recursion ā¦ It was giving TLE, but after setting max. recursive calls, it ran in almost 0.97 sec with ACā¦

I avoided visited placesā¦

I caught the point that if we have cycles then we can actually waste some moves to sum up to M(if we reach last position before M moves)

You could find solution here

We donāt need to compute all primes since N<=40 and we cannot jump more than 37 steps

We can just check in the first 12 primes.

O(1) solution for **SMVOL** using 64-bit integers.

If n = 1 : return 1

Else return 2*(4+3*n*(n-2))

It is derived from the fact that a^3 - b^3 = (a-b)^3 + 3*a*b*(a-b).

Substitute a= n;b = n-2; and solve.

same approach ,that cube term got cancelled

Ya If you consider my solution I am also oscillating inside the bounds 1 to n and not outside the bonds that why I will not go for all primes in my recursive dp. I have just precomputed as I refrain from writing certain checks with if and else and putting such extra things which will obviously not fetch me nothing less than 0.73 sec solution.