HELP | Plot the curve problem | Lenskart Hiring challenge

help
, ,
1

Can someone please provide the editorial of this question.

You are given with integers a, b, c, d, m. These represent the modular equation of a curve y^2 mod\ m = (ax^3+bx^2+cx+d)\ mod\ m

Also, you are provided with an array A of size N. Now, your task is to find the number of pairs in the array that satisfy the given modular equation.

If (A_i, A_j) is a pair then A_j^2\ mod \ m = (aA_i^3+bA_i^2+cA_i+d)\ mod\ m.

Since the answer could be very large output it modulo 10^9 + 7.

Note: A pair is counted different from some other pair if either A_i of the two pairs is different or A_j of the two pairs is different. Also for the convenience of calculations, we may count (A_i, A_j) as a valid pair if it satisfies given constraints.

Input Format

First line of the input contains number of test cases T.
First line for each test case consists of 5 space-separated integers a, b, c, d, m, corresponding to modular equation given.
Next line contains a single integer N.
Next line contains space-separated integers corresponding to values of array A.

Output Format

For each test case, output a single line corresponding to number of valid pairs in the array mod 10^9 + 7.

Constraints

1 \le T \le 10\\ 1 \le N \le10^5\\ -2 \times10^9 \le a,b,c,d,A_i \le 2 \times 10^9\\ 1 \le m \le 2 \times 10^9

Sample Input

1
2 1 -1 3 5
5
10 2 3 14 12

Sample Output

2

Explanation

Equation of curve: y^2=2x^3+x^2-x+3 and m = 5.
Valid pairs satisfying equation of line are (x, y) = (2, 14) and (12, 14). Therefore, the answer is 2.

Note: This question is taken from Hackerearth Lenskart hiring challenge which has already expired.

1 Like
2

This question can be solved in the following manner -

  1. Precompute all the values of a[i]^2 % m for each valid i and store the frequency in a map.
  2. Then for each element calculate the value of the RHS of the equation and just add the occurrences by using values from map .

I am a bit unclear whether i=j is possible or not as it isn’t mentioned in the question, and also about how 2 pairs are counted as distinct, whether it is based on indexing or value.

My solution - link

My solution is based on taking indexes and considers i=j is possible, if it is such that i!=j then just eliminate that pair by checking in step 2. Also if it is such that for 2 distinct pairs, we consider the value and not the index, just remove the duplicates in the beginning.

3

here

is my solution.It got only 40 points what am i doing wrong

4

Please read the question again, your doubt will be cleared.

5

Is it possible to submit this question in practice or can you share the problem link? The basic idea is what I have written above, just a few things need to be changed if i!=j or if it based on value. That is what I want to check.

6

My apologies, the link has been expired.