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 asked 13 Jun '16, 08:42

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(n1) 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*(x1)/2 pairs. answered 13 Jun '16, 09:15
