The dragon type problem of number theory

#1

i am not able to understand the answer of the problem even i checked the editorial but i didn’t get it. please help me explain the solution of the problem.
problem -> https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/practice-problems/algorithm/the-dragon-type-123/

1 Like
#2

In this problem,
Basically you are given with an array of numbers.
your task is to find all the sets of numbers such that (a*b)%m != 0 such that (a*a)%m != 0 and (b*b)%m != 0.
as (a*b)%m = ((a%m)*(b%m))%m, so we are not intersted in what is the numbers given to us, we can simply reduce numbers to a range of m-1 by creating a new array of ai%=m.
After that, we know if (a*b)%m = 1, then b is called the modular multiplicative inverse of a and can be calculated easily using extended euclidian algorithm (ref. Basic Number Theory).
Since we have new array of numbers less than m, if we look for a number in our new array than other number is already decided such that (a*b)%m=1. (b is modular multiplicative inverse).
So, we will remove the other number b from our consideration and then a with any other number will become not equal to 1.
Now, if we calculate the frequencies of all the numbers occuring in our new array, then summation of frequencies of those numbers such that

  1. the modular multiplicative inverse of that number is not the number itself
  2. if modular multiplicative inverse of that number is distinct and lies in our array than we will consider the number with higher frequency between them and will not consider frequency of other (so that it not become equal to 1 and we require maximum size of such beautiful set, so number with higher frequency.)
    That summation will be our answer.

Example:
input is {2, 3, 4, 22, 33} and m is 5.
New array becomes {2, 3, 4, 2, 3};
Frequency of 0 = zero
1 = zero
2 = two
3 = two
4 = one.

Modular multiplicative inverse of 4 is 4 itself, neglect it.
Now modular multiplicative inverse of 2 is 3 and vice versa.
So, the number with higher frequency, and neglect other.
Here, both have frequency of two, So, our answer simply becomes two.

Have a great Day and Keep Learning.
Himanshu Saini
Coding Blocks

1 Like
#3

Great Explaination!!!
Now its completely clear to me
thank you