Mod Pairs

3.6

8 votes
Math, Number Theory, Modulus Arithmetic, C++
Problem

Given an array A of N elements, a prime number P and an integer K. It is guaranteed all the elements in the array are distinct.

Find the number of pairs of indices (i,j) such that (1i<jN) and (A[i]+A[j])×(A[i]2+A[j]2))K mod P 

Note: 1 based indexing is followed.

Input format

  • The first line contains 3 space-separated integers N,P,K.
  • The second line contains N space-separated integers denoting the array A.

Output format

Print the number of pairs of indices which satisfy the given condition in a new line.

Constraints

2N1050K,A[i]P12P105

 

Sample Input
3 3 0
0 1 2
Sample Output
1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • Only 1 pair satisfy the condition i.e. (2, 3)
  • (1+2)×(1+4)=150 mod 3
  • Hence, required answer is 1.
Editor Image

?