CPL01 Editorial

editorial

#1

PROBLEM LINK:

Practice
Contest

Author: Siddhartha Paul
Editorialist: Baban Gain

DIFFICULTY:

EASY

PREREQUISITES:

High School Mathematics

PROBLEM:

A co-prime pair of two numbers P1 and P2 will be given as input and
You have to find how many distinct numbers in a given range of N1…N2 (such that N1 <= n <= N2) which are divisible by either any of the number or both those two numbers.

EXPLANATION:

First we calculate count of numbers divisible by P1 from N1 to N2,

Now, count of numbers divisible by P1 from 1 to N2 is N2 / P1
As we need to count N2 inclusively.
Now, count of numbers divisible by P1 from 1 to N1 -1 is
(N1-1 )/ P1

Hence, count of numbers divisible by P1 from N1 to N2 is (N2 / P1 ) - { (N1-1) / P1}

Similarly,
count of numbers divisible by P2 from N1 to N2 is (N2 / P2 ) - { (N1-1) / P2}

Adding both, total is [ (N2 / P1 ) - { (N1-1) / P1} + (N2 / P2 ) - { (N1-1) / P2} ]

But we have counted numbers that are divisible by P1 and P2 twice.
So, we need to eliminate them once.
No. of double counts = (N2 / L ) - { (N1-1) /L }
where L = LCM( P1 , P2 )
Here as the numbers are co-prime, L = P1 * P2

Hence the final equation is [ (N2 / P1 ) - { (N1-1) / P1} + (N2 / P2 ) - { (N1-1) / P2} ] - [ (N2 / (P1 * P2
) - { (N1-1) / (P1 * P2) } ]

print it MOD 1000000007

Time Complexity: O(1)

AUTHOR’S SOLUTIONS:

Click for Python
Click for C++
Click for Java