ENIGMA08 - Editorial

[sumit.asr_128]

PROBLEM LINK:

Sword in the game

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.

Solution:

Solution Link