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

3 Likes

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

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

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
for(i=b+1;i<=100000;i++)
{
for(j=i;i<=100000;j+=i)
//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’ Nice idea though 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 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

Where can we submit this problem?

2 Likes

1 Like

actually it is a private contest yesterday. But sadly they had disabled all the links Any links to learn mobius function? I’m a newbie and want to learn more about it He has posted the link in his answer. I think you can read it there. Currently reading the same 1 Like

One more link. mobius inversion codeforces

2 Likes

Thankyou bro, I’ll study it 