PROBLEM LINK:
Author: Avinash Verma
Editorialist: Avinash Verma
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Modulo exponentiation
PROBLEM:
Calculate the sum of all powers (up to K) of divisors for numbers from l to r modulo 10^9+7.
QUICK EXPLANATION:
Calculate the contribution of every divisors of numbers from l to r. You will find GP sum for each divisor of all number from l to r.
EXPLANATION:
Question asked you to calculate double summation, if we expand the formula then we see that for each divisors d of numbers from l to r, we have to add d^0 + d^1 + d^2 + d^3 +...+ d^K to our answer.
For each distinct divisors d of numbers form l to r, Lets say numbers of multiple of d from l to r is multd, then we will add ( d^0 + d^1 + d^2 + d^3 + . . . + d^K ) * multd to our answer for each divisors d.
As numbers can vary from l to r, divisors d can vary from 1 to r.
For each number d from 1 to r. we will calculate multi_d from this formula floor(r/d) – floor((l-1)/d) , where floor is a function to return integral part of any numbers.
We can calculate d^0 + d^1 + d^2 + . . . + d^K by GP sum formula i.e (d^{K+1}-1)/(d-1) .
Except for d equal to 1, this formula is not appicable. For d equal to 1 GP sum is simply (K+1) .
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.