Shil and Hill Climbing
Max. Marks 100

Shil decided to go for hill climbing on this weekend, but he doesn’t have the map of all the hills. However he can make his own map.
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 numbers from 1 to N from left to right. The i-th hill has height hi.

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, Shil needs maximum possible size of Beautiful Set.

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

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

Output:
Print maximum possible size of Beautiful Set possible.

Constraints:
2 ≤ N ≤ 105
1 ≤ hi ≤ 1018
2 < p < 105
All the given hi are such that hi % p != 0


Sample Input

(Plaintext Link)

5 5
2 3 4 22 33
Sample Output

(Plaintext Link)

2
Explanation

The two possible Beautiful Sets are {2, 22} and {3, 33}. Here 4 can’t be in 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.

 

 

 

my answer

 

n,p=map(int,raw_input().split())
r=map(int,raw_input().split())
count=0
k=[]
for i in range(n):
if((r[i]*r[i])%p!=1):
k.append(r[i])
for i in range(len(k)):
for j in range(len(k)):
if((k[i]*k[j])%p!=1):
if(i!=j):
#print k[i],k[j]
count+=1
print count/2

 

 

 

Advertisements