ENIGMA08 - Editorial

dynamic-programming
editorial
engm2015
math
medium

#1

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

Solution:

Solution Link