Doubt In Mobius Inversion Question

1

Hi,
I am learning mobius inversion and i encounter a problem which I really didnt know whether this problem can be solve using mobius or not .If (Yes) then tell me how todo with mobius and if (Not) then tell me some other approach to solve this.

question - Given an array of integers (A) and a single integer (B) . Find the number of unordered pairs of (i,j) such that gcd(A[i],A[j]) is greater than (B) {gcd(A[i],A[j]) >B} . Answer should be large so we modulo it with 1e9+7.

This question was not from any ongoing contest .

Link where I encounter above question - Number of pairs with GCD(a[i], a[j]) > 1 - Codeforces

Array length - 1e5
1 <= A(i) <=1e5
1 <= B <= 1e5

1 Like
2

Please specify some conditions, such as the size of n and num.

3

Array length - 1e5
1 <= A(i) <=1e5
1 <= B <= 1e5

4

Using inclusion - exclusion principle

Let 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 A[i]'s in array that are divisible by n
our answer will be \sum_{i=B+1}f(i) .

using mobius function
Let g(i) = iC_2
f(n) = \sum_{i=2 }mu[i]*g(i*n)
where mu[i] is mobius function
our answer will be \sum_{i=B+1}f(i) .