You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 13 Jun '16, 08:42

anil0004's gravatar image

3★anil0004
263
accept rate: 50%


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.

link

answered 13 Jun '16, 09:15

cicil_1995's gravatar image

2★cicil_1995
11
accept rate: 0%

edited 13 Jun '16, 09:22

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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