# 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 the sum of the numbers in a 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:

Let numbers that are divisible by P_{1} from 1 to N_{2} be { P_{1}, 2P_{1},3P_{1}… K_{1}P_{1} }

and numbers that are divisible by P_{1} from 1 to N_{1}-1 be { P_{1}, 2P_{1},3P_{1}… L_{1}P_{1} }

Then numbers that are divisible by P_{1} from N_{1} to N_{2} is

{ P_{1}, 2P_{1},3P_{1}… K_{1}P_{1} } - { P_{1}, 2P_{1},3P_{1}… L_{1}P_{1} }

Sum of them, P_{1} * (1+2+3+…K_{1} ) - P_{1} * (1+2+3+…L_{1}) Or,

#### sum1 = [ P_{1} * K_{1} * (K_{1}+1 )/2 ] - [ P_{1} * L_{1}* (L_{1}+1 )/2 ]

*As, Sum of numbers from 1 upto N = N.(N+1)/2*

Similarly,

Sum of numbers that are divisible by P_{2} from N_{1} to N_{2} is

#### sum2 = [ P_{2} * K_{2} * (K_{2}+1 ) /2 ] - [ P_{2} * L_{2}* (L_{2}+1 )/2 ]

But we have added some numbers twice which are divisible by both P_{1} and P_{2}

So, we need to eliminate them once. Those numbers must be divisible by

M = LCM(P_{1} ,P_{2}) = P_{1} *P_{2} as P_{1} and P_{2} are co-prime.

Let numbers that are divisible by M from 1 to N_{2} be { M, 2M ,3M … XM }

and numbers that are divisible by L from 1 to N_{1}-1 be { M, 2M, 3M, … YM }

Then numbers that are divisible by M from N_{1} to N_{2} is

{ M, 2M ,3M … XM } - { M, 2M, 3M, … YM }

Sum of them, M * (1+2+3+…X) - M * (1+2+3+…Y) Or,

#### extra = [ M * X* (X+1 )/2 ] - [ M * Y* (Y+1 )/2 ]

result = sum1 + sum2 - extra

print result MOD 1000000007