Given three numbers N, A and B. Find how integers in range from 1 to N are divisible by A or B. I can't use modulus operator from range 1 to N because N can be as large as 10^12 and then I would run out of allocated time for the program to produce an output. I have tried formulating the equation but couldn't come up with a solution.
Input Constraints:=
1<=N<=10^12
1<=A<=10^5
1<=B<=10^5
I just want to use some equation to evaluate this thing rather than a modulus operator because the program needs to produce results within 1 sec. I have tried this
counter=(((int)(N/A))+((int)(N/B)))-((int)(N/(A*B)));but it fails for input N=200 A=20 B=8
You are already on the right track, your formula indicates you are trying to apply the inclusion-exclusion principle.
(int) (N/A) and (int) (N/B) corresponds to the counts of integers ≤ N that are dividable by A and B, respectively.
However, (int) (N/(A*B)) does not give you the correct count of integers ≤ N that are dividable by both A and B.
In fact, you should replace (int) (N/(A*B)) by (int) (N/lcm(A,B)) in order to get the correct result. Here lcm(A, B) returns the least common multiple of A and B.
To implement the lcm(A, B) function, you can simply use the following formula:
lcm(A, B) = A * B / gcd(A, B);
where gcd(A, B) returns the greatest common divisor of A and B, and it can be efficiently computed by Euclidean Algorithm, which inevitably involves using the modulus operator only very few times (max {log(A), log(B)} times to be precise), so there should not really be any performance issue for you.