Difficulty : Easy
Pre-requisites : AD-hoc problems experience
At first, the formula for the sum of 14+24+…+n4 is n(1+n)(1+2n)(-1+3n+3n2)/30. The level of the problem is EASY, so the formula can be found on the internet.
At 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