**Problem link** : contest practice

**Difficulty** : Easy

**Pre-requisites** : AD-hoc problems experience

**Solution** :

At first, the formula for the sum of **1 ^{4}+2^{4}+…+n^{4}** is

**n(1+n)(1+2n)(-1+3n+3n**. The level of the problem is EASY, so the formula can be found on the internet.

^{2})/30At second, there are only **sqrt(n)** different values for **[n/i]** over all **i** from **1** to **n**. This fact is also well known and can be proved.

So, the solution is as follows:

- We iterate all the different values of
**[n/i]**. - For each such value
**X**we can calculate the maximal range**[L; R]**such that for each**i**,**L <= i <= R**,**[n/i] = X**. When we have a segment, we can calculate an answer for it, using the above formula in**O(1)**.

So the total time complexity is **O(sqrt N)** per a test case.

**Setter’s solution**: link

**Tester’s solution**: link