SWExShanto's blog

By SWExShanto, history, 9 days ago, In English

How to find how many numbers in range [l, r] are coprime to n where r-l < n? [ in O(sqrt(n)) complexity]


Thanks in advance.

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

You might want to look at Euler Totient function. This function can also be done in O(sqrt(N)) time after factorization.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It can only give us the total number of integers that are coprime to some number. But can it also give the list of those numbers or the list of those who are not coprime to that number under that complexity???

    Thanks in advance!

»
9 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

We will focus on calculating number of numbers coprime to $$$n$$$ which are also less than or equal to a number $$$l$$$. Then we can easily manipulate the result to obtain the answer for a range $$$[l,r]$$$. Also, we could simply solve for finding the numbers which are NOT coprime to $$$n$$$ and are less than or equal to $$$l$$$ and then subtract the result from $$$l$$$ later.

Solution

This approach should work in $$$O(\sqrt{n})$$$ time. The cost of generating subsets is almost constant because the size of the list of prime factors doesn't depend on the value of $$$n$$$ much and it's always less enough to sustain an exponential solution. And prime factorization can be done in $$$\sqrt{n}$$$ time.
I have tried my best to provide a satisfactory explanation but do reply me if any clarification is needed or I have messed up somewhere ':D.
Also I have found an implementation to this problem on the internet.
Link : https://www.geeksforgeeks.org/count-of-natural-numbers-in-range-l-r-which-are-relatively-prime-with-n/

  • »
    »
    9 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Can you give me a direct link to the theory that you have used to solve this part or the name of the theory?

    What we will do is to pick a subset of the list A[], calculate the LCM of the elements of it, let's call it L. Now, if the size of this subset was odd, we add the value of f(L,l) to answer else we subtract it.

    And how generating subsets from a set can be done in that very complexity? It would be more helpful if you added a short explanation for me.

    Thanks in advance!

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no such theory link, but I think it's explainable.
      We first count the numbers which are direct multiples of $$$a_i$$$. Then we subtract the numbers which are direct multiples of $$$a_i\cdot a_j$$$ (because we have counted them twice, once with $$$a_i$$$ and once with $$$a_j$$$). But in this process we have nullified the contribution of $$$a_i\cdot a_j\cdot a_k$$$ (added with $$$a_i,a_j,a_k$$$ and subtracted with $$$a_i\cdot a_j,a_j\cdot a_k,a_k\cdot a_i$$$). So we should add the contribution of subset of size three. Similarly subtracting for size four and so on...

      And for the case with bitmasking approach, it will take exponential time. But the size of the list of prime factors is at most $$$11$$$ (considering $$$1\leq n\leq 10^{12}$$$). So, a bitmasking approach will always work within the needed time complexity.