PROBLEM LINK:
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.
