COG1804 - Editorial

PROBLEM LINK:

Practice

Contest

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.

Little Appreciation Keeps us Motivated.

//