Help in a GCD problem

Given an array of integers (A[i] <= 10^5). We have to find number of unordered pairs (i, j) such that their GCD is greater than B.


where is this ques frm??
hav u tried brute force with memoization?

1 Like

There is a O(N*(√a(i)) algorithm. I’ll write the solution after my endsem :slight_smile:

what is here to memoize for?

I have tried O(N^2) which obviously not going to pass.

can you please just share rough idea?

How about this?
Let us consider the elements a,b
For gcd(a,b) to be exactly k both a>=k and b>=k and a%k==0 and b%k==0.
for example take k=5,for gcd(a,b) to be exactly 5 the possible no. are a combination of any two multiples of 5 present in the array.
let the array be 1,5,10,4,15,6,20.
the no. are multiple of 5 are 4(say,x)— 5,10,15,20 .GCD=5 is for combination of any two (5,10),(5,15),(5,20),(10,15),(15,20) but not(10,20) . So,Here you have to check the gcd by euler’s method which is log(max(a,b))
(Hope this is clear).

Now the answer in constraints…since(a[i]<=10^5).
use a hashmap or an array to count the occurence of every element
for every no. >B Find the no. of multiples that number in the array and hence the no. of pairs with gcd equal to that no.(Answer will be the sum of all these).
Iterate like this
//code where we count the multiples of i in the array.
//check if this gcd(i,j) pair is valid.
let max=100000
Worst case when b=1;
loop runs sequence will be like = (max/1) + (max/2) + (max/3) +…+max/100000 <= 1300000 = O(10^6 * log(max)). This might clear the 1 sec time limit though.

Your approach will fail cuz there can be many numbers greater than B , but they might be having their gcd less than ‘B’ :slight_smile:
Nice idea though :slight_smile:

my approach had an error actually now updated it.But @anon55659401 i am looking for pairs where exact gcd=x where a,b are sure multiple of x,and checking on them only,i cant find the error here that you are mentioning though.
it would be nice of you if you point out at example.

There is one more fault in your approach, you are counting many pairs repeatedly…

+I think its bound to give TLE :frowning:

The worst case time complexity is still less than O(n*sqrt(a[i])) though that you suggested.

This problem can be solved using mobius inversion (inclusion - exclusion principle).
Le f(n) = number of unordered pairs(i,j) such that their gcd is n
then f(n)=NC_2 -(\sum_{i=2 }f(i*n))
where N = no. of numbers in array that are divisible by n
our answer will be \sum_{i=B+1}f(i)

Where can we submit this problem?


Thanks for you reply!

If possible then can you please help me with this problem also.

please send the link to the above gcd question…

1 Like

actually it is a private contest yesterday. But sadly they had disabled all the links :frowning:

Any links to learn mobius function? I’m a newbie and want to learn more about it :slight_smile:

He has posted the link in his answer. I think you can read it there. Currently reading the same :slight_smile:

1 Like

One more link. mobius inversion codeforces


Thankyou bro, I’ll study it :slight_smile: