GOODNUMB - Editorial (LOCJUN16)

Problem Link

Contest
Practice

Author: Praveen Dhinwa
Editorialist: Vaibhav Tulsyan

Difficulty

Easy

Pre-requisites

Sieve of Eratosthenes

Problem

Find the sum of divisors of good numbers between L and R, such that a good number is square-free and the number of prime numbers dividing the sum of its divisors is prime.

Quick Explanation

Uptil 5 * 105, pre-compute for each number whether it is square-free, whether it is a prime number and its sum of divisors.
Use prefix sum to store the sum of divisors of all good numbers uptil i.
Answer for each test case = prefix_sum uptil [R] - prefix_sum uptil [L - 1]

Detailed Explanation

  1. Prime Numbers
    Knowing the implementation of Sieve of Eratosthenes can be helpful in solving the problem. The sieve method can be used to find all prime numbers upto a certain integer N.

  2. Square free numbers

Use a method similar to the Sieve of Eratosthenes.
Maintain a boolean array, in which if the ith index is marked true, then the integer i is square-free, else it is not.
For each integer, mark all multiples of its square as not-square-free. Hence, we are left with only square-free numbers.

  1. Counting divisors and sum of divisors

Consider a certain integer X - we know that X would be a proper divisor of the numbers X, 2*X, 3*X, …, K*X.
If the limit upto which we want to store divisors is Y, we know that K*X \le Y.
The implementation of this method is again similar to the Sieve of Eratosthenes.

  1. Good Numbers

For each integer i, we can compute whether it satisfies both conditions of a good number or not.

  1. Prefix Sum

To keep track of the sum of divisors of all good numbers uptil i, we store the cumulative sum of divisors of good numbers uptil i.

After all the pre-computation, we need to find out the sum of divisors of good numbers between L and R. For doing that, we used a standard prefix sum technique:

prefix_sum uptil [R] - prefix_sum uptil [L - 1]

@wittyceaser @admin2 Please provide editorials or some help for the problem ‘Maximum Disjoint Subarrays (MXSUBARR)’.

1 Like

Will be uploaded as soon as possible. Will publish editorials for all problems!