# PROBLEM LINK:

**Author:** Siddhartha Paul

**Editorialist:** Baban Gain

# DIFFICULTY:

EASY

# PREREQUISITES:

High School Mathematics

# PROBLEM:

A co-prime pair of two numbers P_{1} and P_{2} will be given as input and

You have to find how many distinct numbers in a given range of N_{1}…N_{2} (such that N_{1} <= n <= N_{2}) which are divisible by either any of the number or both those two numbers.

# EXPLANATION:

First we calculate count of numbers divisible by P_{1} from N_{1} to N_{2},

Now, count of numbers divisible by P_{1} from 1 to N_{2} is N_{2} / P_{1}

As we need to count N_{2} inclusively.

Now, count of numbers divisible by P_{1} from 1 to N_{1} -1 is

(N_{1}-1 )/ P_{1}

Hence, count of numbers divisible by P_{1} from N_{1} to N_{2} is **(N _{2} / P_{1} ) - { (N_{1}-1) / P_{1}}**

Similarly,

count of numbers divisible by P_{2} from N_{1} to N_{2} is **(N _{2} / P_{2} ) - { (N_{1}-1) / P_{2}}**

Adding both, total is **[ (N _{2} / P_{1} ) - { (N_{1}-1) / P_{1}} + (N_{2} / P_{2} ) - { (N_{1}-1) / P_{2}} ]**

But we have counted numbers that are divisible by P_{1} and P_{2} twice.

So, we need to eliminate them once.

No. of double counts = (N_{2} / L ) - { (N_{1}-1) /L }

where L = LCM( P_{1} , P_{2} )

Here as the numbers are co-prime, L = P_{1} * P_{2}

Hence the final equation is **[ (N _{2} / P_{1} ) - { (N_{1}-1) / P_{1}} + (N_{2} / P_{2} ) - { (N_{1}-1) / P_{2}} ] - [ (N_{2} / (P_{1} * P_{2}**

) - { (N_{1}-1) / (P_{1} * P_{2}) } ]

print it MOD 1000000007