find no of unordered pair(a,b) where (a*b)%m=0

we are given positive integer a1,a2,a3,an and m.we have to find no of unordered pair(a,b) where (a*b)%m=0.

e.g
(a1,a2,a3,an) = (2,3,22,7,23)

m = 7

ans = 4

Case 1:

If there is any integer n which is the multiple of m, then we have len(array)-1 pairs satisfying (ab)%m = 0. If there are x such integers exists and n is the size of the array, then we have x(n-1) pairs satisfying (ab)%m==0 where a,b belongs to array and any one of a,b is the multiple of m. This is based on the fact that, (ab)%m = (a%m*b%m)%m, if a or b is a multiple of m, then it will be made 0 and hence the answer will be 0 too.

Case 2:

Another one will be, Factorize the m, check for it’s factors in the array…if m has n factors and out of these n factors, x factors will be present in the array, then you have x*(x-1)/2 pairs.

//