bansal1232's blog

By bansal1232, history, 5 years ago, In English

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.

Constraints

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

Sample Input

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

Sample Output

2

Explanation

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Create two maps, one of the LHS and the other of the RHS, for each element. Then iterate over the common values and add the product of their frequencies in both the maps.