### PROBLEM LINK:

**Author and Editorialist :** Sunny Karira

### Difficulty

Medium

### Pre-requisites

Dynamic Programming, Math

### Problem

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].

### Quick Explanation

This problem can be solved using inclusion-exclusion principle.

### Explanation

If 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.