xennygrimmato's blog

By xennygrimmato, 4 years ago, In English,

Q. Given an array of N positive integers, find all pairs (ai, aj) such that Gcd(ai, aj) > 1.

1 ≤ N ≤ 105

How can this problem be solved?

GCD Recruit — HackerEarth

Tags gcd
 
 
 
 
  • Vote: I like it  
  • +9
  • Vote: I do not like it  

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this problem from?

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

Just look closer at the constraints :) It also can be solved for A[i] <  = 106 .

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give another hint? I first thought precomputing euler totient function for all A[i] ≤ 3000 might be useful, but I dont think that will help.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I solved a similar problem on codechef a while ago, the key idea is to use inclusion-exclusion principle. If a number X is a multiple of Y, then X is also a multiple of all of Y's divisors. Now count for each number Y, the number of it's multiples that are present in your array and then apply inclusion-exclusion by making a loop from the highest Y to 1 and excluding every number's divisors.

The problem can be solved using mobius inversion formula but I don't understand it quite well but you can find pretty good tutorials about it on the internet!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you link me to the codechef problem ?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I contemplated over the idea but I am thinking that I need to know how many multiples of particular i <=10^6 are present in array how will that be processed efficiently! !please explain the process clearly !!

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The problem constraints say that the largest number in the input will be less than 10^6 so here is what you can do. Put all number in a hash map with the frequency of each number.

      Now say that you want to find how many multiples of 2 there are, you will go through the hash map and sum the counts of 2, 4, 6, 8, 10, 12, ...... 10^6

      This will take time roughly equal to 10^6/2.

      Now if you want to do the same thing for other numbers X from 3 to n, everyone will take (10^6/X) so the total time complexity would be 10^6/2 + 10^6/3 + 10^6/4 + 10^6/5 + ...... 10^6/n

      This is equal to 10^6*(1/2 + 1/3 + 1/4 + 1/5 ..... + 1/n). The summation from 1/1 to 1/n is called harmonic series and is bounded by O (ln (n))

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I bit of more explanations would be highly appreciated!

    • »
      »
      »
      6 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      As there are atmost 8 distinct primes that a number can have a[i]<=10^6 , when we are at an index i we find how many of the numbers from 1 to i-1 have atleast one common divisor with the a[i] this can be done by PIE(PRINCIPLE OF INCLUSION AND EXCLUSION) ,we keep a global array G[] which tells us the number of elements which are divisible by the the index ,i.e G[i] = denotes number of elements uptill now which have i as one of it's divisors,to find no of elements from 1 to i-1 we use PIE and as our current number has atmost 8 distinct divisors say p1,p2,p3,...p8 then with PIE we can find total number of elements which are divisible by atleast one of the p1,p2,p3,...p8 ..we need G[p1 U p2 U p3 ...p8]= sigma G[pi] — sigma G[pi ^ pj] + sigma G[pi ^ pj ^pk] ......so on {^ =denotes intersection} time complexity of this step is 2^8 and after this step we will update G[] and increament at all positions where the a[i] is divisible similarly by generating 2^8 possible distinct prime combinations so overall time complexity = O(N*2^8).

      upd: try this one this is based on modified PIE https://www.hackerearth.com/problem/algorithm/altered-primes/description/

»
4 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

my algorithm for this problem went through about 2.7*10^7 operations. The basic idea was to have 2 for loops, one going from 1 to 3000 [say with variable i] and the other from 1 to 3000 [with variable j]. Then, if the gcd of the two is >0, and they are not the same, then you add X[i]*X[j] to one counter, where X[i] is the number of occurrences of integer i in the list provided. Else, if the gcd is > 0 and they are the same, then add X[i]*(X[i]-1)/2 to a separate counter. If we let the first counter be a and the second b, the answer is (a/2)+b

Note: This approach is much much easier then exclusion-inclusion principle.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    ur idea is correct, but i think the answer should be instead of .

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      no it should be (a/2)+b, as we are not counting each pair b twice (for example, (2,2) is only counted once).

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        let a = [1, 2, 2, 3]. the correct answer for this case is 1 (only the pair (2, 2) is valid).
        but according to ur method, x = [1, 2, 1]. this gives answer as 2, which is wrong.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh I'm sorry... I mistyped when I put down my algorithm :P

          It is fixed [it should be x[i]*(x[i]-1)/2]

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    They used the inclusion-exclusion principle to solve it when A[i]<=10^6

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What if A[i]<=107