PROBLEM LINK:Author and Editorialist : Sunny Karira DifficultyMedium PrerequisitesDynamic Programming, Math ProblemTo find the damage done by golden sword and the damage will be calculated as the number of numbers on the slice of [1,N]. Quick ExplanationThis problem can be solved using inclusionexclusion principle. ExplanationIf f_{a1a2..ak}(n) is the answer, then the following formula works: f_{a1a2..ak}(n) = f_{a2a3..ak}(n)  f_{a2..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. Solution:
This question is marked "community wiki".
asked 16 Oct '15, 22:17
