HELP | Plot the curve problem | Lenskart Hiring challenge

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.


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

2 1 -1 3 5
10 2 3 14 12

Sample Output



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

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.


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

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

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.

My apologies, the link has been expired.