HELP | Looking for editorial | Lenskart Hiring challenge problem

Revision en1, by bansal1232, 2019-01-28 15:39:28

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 y2 mod m = (ax3 + bx2 + 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 (Ai, Aj) is a pair then Aj2 mod m = (aAi3 + bAi2 + cAi + d) mod m.

Since the answer could be very large output it modulo 109 + 7.

Note: A pair is counted different from some other pair if either Ai of the two pairs is different or Aj of the two pairs is different. Also for the convenience of calculations, we may count (Ai, Aj) 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 109 + 7.


1 ≤ T ≤ 10,  1 ≤ N ≤ 105,   - 2 × 109 ≤ a, b, c, d, Ai ≤ 2 × 109,  1 ≤ m ≤ 2 × 109

Sample Input

2 1 -1 3 5
10 2 3 14 12

Sample Output



Equation of curve: y2 = 2x3 + x2 - 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.

Tags #help, #math, modular arithmetic


  Rev. Lang. By When Δ Comment
en1 English bansal1232 2019-01-28 15:39:28 1814 Initial revision (published)