All Tracks Math Number Theory Basic Number Theory-1 Problem

The Dragon Type
Tag(s):

Medium, Number Theory

Problem
Editorial
Analytics

Dragonite decided to go for hill climbing this weekend, but he doesn't have the map of all the hills. However he can make his own map. Since, well, he's a dragon, du'uh.

There are $$N$$ hills arranged on a line, each in the form of a vertical line segment with one endpoint on the ground. The hills are numbered with integers from $$1$$ to $$N$$ from left to right. The ith hill has height hi.

A beautiful set $$S$$ is set of hills such that for any hi, hj present in set $$S$$, (hi * hj)%p!=1.

Note that here i can be equal to j. Here $$p$$ is any prime integer. To make the map, Dragonite needs maximum possible size of the beautiful set.

Note that two sets are considered different if they contain at least one point which is different. Two sets are considered same if they contain the same points.

Input format:
The first line of input contains two integers $$N$$, the number of hills and a prime number $$p$$. The next $$N$$ lines contains the height of the hills.

Output format:
Print the maximum possible size of the beautiful set possible.

Constraints:
2 ≤ $$N$$ ≤ 2 * 105
1 ≤ hi ≤ 1018
2 < $$p$$ < 105

References:
enter image description here

SAMPLE INPUT
5 5
2 3 4 22 33
SAMPLE OUTPUT
2
Explanation

The two possible Beautiful Sets are {2,22} and {3,33}. Here 4 can't be any beautiful set because (4 * 4) % 5 =1 .Also 2 and 3 can't be in any beautiful set because (2 * 3) % 5 = 1. Also note that (2 * 22) % 5!=1 and (3 * 33) % 5!=1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications