Author and Editorialist : Sunny Karira
Dynamic Programming, Math
To find the damage done by golden sword and the damage will be calculated as the number of numbers on the slice of [1,N].
This problem can be solved using inclusion-exclusion principle.
If fa1a2…ak(n) is the answer, then the following formula works:
fa1a2…ak(n) = fa2a3…ak(n) - fa2…ak(floor(n/a1))
But if you write only this recursive function, you get TLE.
The quickest approach was to solve the question using DP and memorize the answers for small n and all ai.