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