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?
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
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
our answer will be \sum_{i=B+1}f(i)
Where can we submit this problem?
2 Likes
Thanks for you reply!
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
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
Thankyou bro, I’ll study it