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