i didnt get it. do you mean just the numbers between L R or there is a array and you want this for ai -> L <= i <= R!? but in these kind of problems there are some solution that works with this -> add edge between them (if you get the numbers or indexes as a node) and then you want the number of edges in range L, R. and you can do this with segment tree. there is a similar problem "Yaroslav and Divisors"

Auto comment: topic has been updated by darth_chef (previous revision, new revision, compare).

You can do some inclusion-exclusion/Mobius stuff to solve this.

Let's fix a particular $$$x$$$. Note that it suffices for us to be able to count the number of integers coprime with $$$x$$$ in the range $$$[1,n]$$$, for some $$$n$$$.

All uses of / indicate integer division, by the way.

Let's suppose $$$x = 12$$$. Let's initialize a variable count = n, since initially there are $$$n$$$ numbers in the given range. A number is definitely not coprime with $$$x$$$ if it has a common prime factor with $$$x$$$. So, let's remove all the multiples of $$$2$$$ and all multiples of $$$3$$$, since those definitely arent coprime with $$$12$$$. We do count -= n/2 and count -= n/3. However, when we did this, we subtracted all multiples of $$$6$$$ twice when we really only should have to subtract them once. We account for this by adding back in count += n/6.

Great, let's look at another example. Suppose $$$x = 700$$$. Again, we begin at count = n. Then, remove all multiples of $$$2$$$, $$$5$$$, and $$$7$$$, so count -= n/2, count -= n/5, and count -= n/7. This time, we double-counted the multiples of $$$10$$$, $$$14$$$, and $$$35$$$ (the ones where two distinct prime factors showed up). So, we add back in count += n/10, count += n/14, and count += n/35. However, now we are under-counting the multiples of $$$70$$$ (where all three prime factors appear), so we do again count -= n/70.

In general, we get the following inclusion-exclusion for $$$x$$$:

• Let count := n initially
• Then, -= update for all prime divisors of $$$x$$$.
• Then, += update for all divisors of $$$x$$$ that are exactly two distinct prime factors.
• Then, -= update for all divisors of $$$x$$$ that are exactly three distinct prime factors.
• And so on...

This information is captured succinctly in the Mobius function, which you can Google, but long story short, we have a function $$$\mu$$$ such that $$$\mu(d) = 0$$$ if $$$d$$$ is not squarefree; otherwise, $$$\mu(d)=1$$$ if $$$d$$$ has an even number of prime factors, and $$$\mu(d)=-1$$$ if $$$d$$$ has an odd number of prime factors (this describes the inclusion-exclusion alternating parity seen above).

Then, for our counting problem, the answer is

where $$$f(d) = n/d$$$. As you can see, $$$\mu$$$ is just a compact way of saying whether you should add, subtract, or ignore a given divisor to match the inclusion-exclusion formulation. You can look up how to quickly compute $$$\mu(d)$$$ for all $$$d$$$ from $$$1$$$ to $$$n$$$ using a sieve.

Thus, the complexity to answer for a single value of $$$x$$$ is $$$\tau(x)$$$, the number of divisors of $$$x$$$. The worst case complexity to answer all $$$x$$$ in the range $$$[1,n]$$$ is

can you please share the problem link?