bansal1232's blog

By bansal1232, history, 7 months 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

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Code. Basically you create an array/vector of numbers 0-4, and then whatever the equation outputs for every possible x, you take the sum of size of the elements in that particular position of the array and output it .

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    There are many flaws in your solution. Please cross check it once.

»
7 months 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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Java code for the same. Idea is to take two arrays, one for storing y2ModM values and another for values of the cubic equation mentioned. There could be scenario where for two different x, the values in y2ModM is same. Take x = -1, +1 for example. So we maintain a map taking the values in y2ModM array as key and count of it as value and check for each item in the cubicEquation arr, if that matches with anything in y2ModM array.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Test8 {
    private static BigInteger MODULO_M = null;
    private static final BigInteger MODULO = BigInteger.valueOf(1000000007);

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bufferedReader.readLine().trim());
        while (T-- > 0) {
            String[] input1 = bufferedReader.readLine().trim().split(" ");
            int a = Integer.parseInt(input1[0]);
            int b = Integer.parseInt(input1[1]);
            int c = Integer.parseInt(input1[2]);
            int d = Integer.parseInt(input1[3]);
            int m = Integer.parseInt(input1[4]);

            int N = Integer.parseInt(bufferedReader.readLine().trim());
            String[] input2 = bufferedReader.readLine().trim().split(" ");
            int[] arr = new int[N];

            BigInteger[] y2ModMArr = new BigInteger[N];
            BigInteger[] polynomialFunctionValues = new BigInteger[N];

            MODULO_M = BigInteger.valueOf(m);

            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(input2[i]);
                BigInteger num = BigInteger.valueOf(arr[i]).mod(MODULO_M);
                BigInteger numSq = num.multiply(num).mod(MODULO_M);
                BigInteger numCubed = numSq.multiply(num).mod(MODULO_M);
                polynomialFunctionValues[i] = BigInteger.valueOf(a).mod(MODULO_M).multiply(numCubed).mod(MODULO_M).add(BigInteger.valueOf(b).mod(MODULO_M).multiply(numSq).mod(MODULO_M)).add(BigInteger.valueOf(c).mod(MODULO_M).multiply(num)
                        .mod(MODULO_M)).add(BigInteger.valueOf(d).mod(MODULO_M)).mod(MODULO_M);
                y2ModMArr[i] = numSq;
            }


            BigInteger result = BigInteger.ZERO;
            Map<BigInteger, Integer> y2ModMap = new HashMap<>();
            for (int i = 0; i < N; i++) {
                int count = 1;
                if (y2ModMap.containsKey(y2ModMArr[i])) {
                    count += y2ModMap.get(y2ModMArr[i]);
                }
                y2ModMap.put(y2ModMArr[i], count);
            }

            for (int i = 0; i < N; i++) {
                if (y2ModMap.containsKey(polynomialFunctionValues[i]))
                    result = result.add(BigInteger.valueOf(y2ModMap.get(polynomialFunctionValues[i]))).mod(MODULO);
            }

            System.out.println(result.longValue());
        }
    }
}

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are you 100% sure about your solution? I mean, the link has been expired therefore I couldn't verify this one.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It passed all test cases :)

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok,then please explain your approach or put relevant comments in the code. Thanks

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Is your code not failing on this test case.

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

          Correct answer should be 2.--> (2, 14), (12, 14).

          But your code is printing 3 because it's counting (2, 14) pair two times.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Did you really try running the code?

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I had also used the same technique while submitting the code that you mentioned but got WA.

              I just wanna know, what will be the output of above test case according to you?