CDSW153 - Editorial

PROBLEM LINK:

Practice

Contest

Author: Man Mohan Mishra

Editorialist: Swapnil Saxena

DIFFICULTY:

MEDIUM

PREREQUISITES:

Inclusion-Exclusion Principle, Bitmasking

EXPLANATION:

The problem is to find the count of positive integers in range [L, R] that are divisible by atleast one prime in range [1, N]. One thing to observe here is N <= 50 and upto 50 there are only 15 primes. Now say we have a set of primes 1 < p1, p2, p3, …, pk <= N. The count of integers divisible by atleast one of them is given be ∑f(prime) - ∑ f(a product of exactly two primes) + ∑ f(a product of exactly three primes) - …where f(X)is the count of multiples of X in [L, R].

(Note: f(X) = [ R / X ] – [ (L-1) / X] where [.] is the floor function)

Simply put, this follows the ‘Set Inclusion Exclusion Principle’. So to calculate the answer, generate all possible subsets of of primes and if the size of this subset is odd add f(X) to the answer where X = products of all primes in the set to the answer. Substract it otherwise.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.

How do I generate all the subsets of prime numbers? for 15 numbers, there will be 2^15=32768 subsets. How do I generate them all?

And could you tell me how did this solution get accepted? Only the product of two prime numbers has been considered here.
http://www.codechef.com/viewsolution/6349937

1 Like

@prateekjjw001 : To generate all the subsets in 215 time complexity, you can apply this concept

Got it. Thanks :slight_smile: