PROBLEM LINKS:
Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit
DIFFICULTY:
MEDIUM
PROBLEM:
In this problem, we had to find the count of numbers between a range[R,L] such that their GCD with N is X.
EXPLANATION:
It would be the same as finding the count of numbers between L/X and R/X such that their GCD with N/X is 1. This is because if divide two numbers by their GCD then the resulting numbers would be coprime. So the task remains to find the count of numbers between a range which are coprime to N.
Let f© be the number of integers from 1 to A which are coprime to N.
So we can calculate our answer as f®-f(L-1).
f© is A minus the number of integers that are not relatively prime to N.
Call this number g©. So f©=C−g©. We attack the problem of finding g©.
If N is a prime power p^a, it is easy.
The numbers in the interval [1,C] that are not relatively prime to N are the multiples of p.
Thus
g©=⌊C/p⌋
where ⌊x⌋ is the usual “floor” function.
If N has prime power factorization p^a*q^b, where p and q are distinct primes, then g© is the number of integers in [1,C] that are divisible by p or q or both. By Inclusion/Exclusion, we obtain
g©=⌊C/p⌋+⌊C/q⌋−⌊C/pq⌋.
The reason is that when we add the first two terms above, we are counting twice all the multiples of pq.
If N has prime power factorization p^a*q^b*r^c, the same basic idea works. We get
g©=⌊C/p⌋+⌊C/q⌋+⌊C/r⌋−⌊C/qr⌋−⌊C/pr⌋−⌊C/pq⌋+⌊C/pqr⌋.
The number of distinct primes for a number less than 10^9 will not be greater than 9. So bitmasking can be used to calculate all product combinations and then calculating f® and f(L-1). Each query can be answered in
O(2^number of distinct primes).
AUTHOR’S SOLUTION:
Author’s solution can be found here.