CPL02 Editorial

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 the sum of the numbers in a range of N1…N2 (such that N1 <= n <= N2) which are divisible by either any of the number or both those two numbers.

EXPLANATION:

Let numbers that are divisible by P1 from 1 to N2 be { P1, 2P1,3P1… K1P1 }
and numbers that are divisible by P1 from 1 to N1-1 be { P1, 2P1,3P1… L1P1 }

Then numbers that are divisible by P1 from N1 to N2 is
{ P1, 2P1,3P1… K1P1 } - { P1, 2P1,3P1… L1P1 }

Sum of them, P1 * (1+2+3+…K1 ) - P1 * (1+2+3+…L1) Or,

sum1 = [ P1 * K1 * (K1+1 )/2 ] - [ P1 * L1* (L1+1 )/2 ]

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

Similarly,
Sum of numbers that are divisible by P2 from N1 to N2 is

sum2 = [ P2 * K2 * (K2+1 ) /2 ] - [ P2 * L2* (L2+1 )/2 ]

But we have added some numbers twice which are divisible by both P1 and P2
So, we need to eliminate them once. Those numbers must be divisible by
M = LCM(P1 ,P2) = P1 *P2 as P1 and P2 are co-prime.

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

Then numbers that are divisible by M from N1 to N2 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

Time Complexity: O(1)

AUTHOR’S SOLUTIONS:

Click for Python
Click for C++
Click for Java