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
I solved this problem without using Mobius inversion.
My AC Solution link : Code
First we precompute all the divisors for each number upto 10^5 and store it in a vector. Then for each number, we count the number of times it appears as a divisor in our original array.
Let’s call the newly constructed array as cnt. Note that gcd(a,b)=x then it implies that a%x=0 and b%x=0.
Now we construct a dp array where dp[i] is the number of pairs where gcd=i. To get the values of dp[i] we will run a loop from maximum number in the array(since gcd of two numbers cannot be greater than the minimum of two numbers) down to m. For each i, we initialize dp[i]=(cnt[i]*(cnt[i]-1)/2).
Suppose our array is [10,20,40] and k=10. Then in our case dp[10] will count (20,100) as a pair and dp[20] will also count (20,100) as a pair. So now we need to get rid of the duplicate pairs. To remove this we will run a inner loop of j from 2*i upto maximum value and increment j by i at every iteration. In this loop we will decrement dp[i] by dp[j] i.e. dp[i]-=dp[j]. Thus in our example dp[20] will count the pair (20,100) but dp[10] will not as 10 is itself a divisor of 20.
Our answer is sum of dp[i] from i=max value upto i=k.
The Time Complexity of the above approach is O(tnlogn) where t<=10 and n<=10^5 which will easily pass the time limit. Note that if you don’t precompute divisors then it will result in TLE.
Hope this helps !!!
5 Likes
Thanks a lot for your explanation. I was not able to remove the duplicates, when I was trying the question yesterday in the contest. Now your approach of removing duplicates seems quite intuitive 
1 Like