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* ≤ 10^{5}

How can this problem be solved?

# | User | Rating |
---|---|---|

1 | tourist | 3509 |

2 | OO0OOO00O0OOO0O0…O | 3327 |

3 | Syloviaely | 3274 |

4 | Um_nik | 3237 |

5 | Petr | 3161 |

6 | ko_osaga | 3154 |

7 | LHiC | 3135 |

8 | Benq | 3130 |

9 | Swistakk | 3089 |

10 | dotorya | 3060 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 185 |

2 | rng_58 | 161 |

3 | tourist | 158 |

4 | Petr | 152 |

5 | Vovuh | 150 |

5 | Swistakk | 150 |

7 | PikMike | 147 |

8 | csacademy | 146 |

9 | Errichto | 145 |

9 | Um_nik | 145 |

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* ≤ 10^{5}

How can this problem be solved?

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2018 11:15:46 (f1).

Desktop version, switch to mobile version.

User lists

Name |
---|

Where is this problem from?

http://www.hackerearth.com/problem/algorithm/gcd-recruit/

Just look closer at the constraints :) It also can be solved for

A[i] < = 10^{6}.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.I solved a similar problem on codechef a while ago, the key idea is to use inclusion-exclusion principle. If a number

Xis a multiple ofY, thenXis also a multiple of all ofY's divisors. Now count for each numberY, the number of it's multiples that are present in your array and then apply inclusion-exclusion by making a loop from the highestYto 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!

Can you link me to the codechef problem ?

Here you go http://www.codechef.com/problems/COPRIME3

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 !!

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))

I bit of more explanations would be highly appreciated!

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/

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.

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

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

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.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]

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

oh, makes sense.

What if A[i]<=10

^{7}