×

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

 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 asked 13 Jun '16, 08:42 3★anil0004 26●3 accept rate: 50%

 0 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. answered 13 Jun '16, 09:15 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×625
×333

question asked: 13 Jun '16, 08:42

question was seen: 885 times

last updated: 13 Jun '16, 09:22