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 **h _{i}**.

**Beautiful set S** is set of hills such that for any **h _{i}, h_{j}** present in set

**S**,

**(h**. Note that here

_{i}* h_{j})%p != 1**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** ≤ 10^{5}

1 ≤ **h _{i}** ≤ 10

^{18}

2 <

**p**< 10

^{5}

All the given

**h**are such that

_{i}**h**

_{i}% p != 0The 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

February 1, 2016 at 1:26 pm

for i in range(n):

if((r[i]*r[i])%p!=1):

k.append(r[i])

Could you explain this for loop is for?

LikeLiked by 1 person

February 1, 2016 at 3:46 pm

ya i did that because condition states that..

Beautiful set S is set of hills such that for any hi, hj present in set S , (hi * hj)%p != 1,and i can be equal to j.

so ,

remove all the numbers at the beginning which violates that rule.

I created new list with numbers which obeys that rule.

I hope it clarifies your doubt.

LikeLike