### xennygrimmato's blog

By xennygrimmato, 6 years ago, ,

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

1 ≤ N ≤ 105

How can this problem be solved?

GCD Recruit — HackerEarth

• +9

 » 6 years ago, # |   0 Where is this problem from?
•  » » 6 years ago, # ^ |   +3
•  » » » 10 months ago, # ^ |   0 The link is not working.
 » 6 years ago, # | ← Rev. 2 →   +9 Just look closer at the constraints :) It also can be solved for A[i] <  = 106 .
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +4 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!
•  » » 6 years ago, # ^ |   0 Can you link me to the codechef problem ?
•  » » » 6 years ago, # ^ |   +4 Here you go http://www.codechef.com/problems/COPRIME3
•  » » 2 years ago, # ^ |   0 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 !!
•  » » » 2 years ago, # ^ |   +5 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^6This 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/nThis 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))
•  » » 2 years ago, # ^ |   0 I bit of more explanations would be highly appreciated!
•  » » » 2 years ago, # ^ | ← Rev. 5 →   0 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/
•  » » » » 10 months ago, # ^ |   0 can i get the code for this?
•  » » » » » 10 months ago, # ^ |   0 haha! searching for star values eh??
•  » » » » » » 10 months ago, # ^ | ← Rev. 2 →   0 .
•  » » » » » » 10 months ago, # ^ |   0 Good catch bro
•  » » » » 10 months ago, # ^ |   0 Can u atleast refer me some problems using this concept? Thanks in advance.
 » 6 years ago, # | ← Rev. 4 →   0 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)+bNote: This approach is much much easier then exclusion-inclusion principle.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 ur idea is correct, but i think the answer should be instead of .
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 no it should be (a/2)+b, as we are not counting each pair b twice (for example, (2,2) is only counted once).
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   0 Ohh I'm sorry... I mistyped when I put down my algorithm :PIt is fixed [it should be x[i]*(x[i]-1)/2]
•  » » 6 years ago, # ^ |   +3 They used the inclusion-exclusion principle to solve it when A[i]<=10^6
•  » » » 6 years ago, # ^ |   0 oh, makes sense.
 » 4 years ago, # |   0 What if A[i]<=107
 » 15 months ago, # |   +9 Hello everyone, I came across a similar problem -- for a vector a, display number of unordered pairs such that GCD(a[i],a[j])>b such that i!=j. a[] and b are given in the input. Please help.
•  » » 15 months ago, # ^ |   +11 Where is this problem from?
 » 15 months ago, # |   0 Find the number of coprime pairs in the array using mobius inversion, then subtract it from total pairs.