Count Pairs (Codeforces 1188B)
Tags: Math, matrices

You are given a prime number $$$p$$$, $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, and an integer $$$k$$$. Find the number of pairs of indexes $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) for which $$$(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$$$.

Input: The first line contains integers $$$n, p, k$$$ ($$$2 \le n \le 3 \cdot 10^5$$$, $$$2 \le p \le 10^9$$$, $$$0 \le k \le p-1$$$). $$$p$$$ is guaranteed to be prime.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le p-1$$$). It is guaranteed that all elements are different.

Output: Output a single integer — answer to the problem.

Note: In the first example:$$$(0+1)(0^2 + 1^2) = 1 \equiv 1 \bmod 3$$$.$$$(0+2)(0^2 + 2^2) = 8 \equiv 2 \bmod 3$$$.$$$(1+2)(1^2 + 2^2) = 15 \equiv 0 \bmod 3$$$.So only $$$1$$$ pair satisfies the condition.In the second example, there are $$$3$$$ such pairs: $$$(1, 5)$$$, $$$(2, 3)$$$, $$$(4, 6)$$$.

Sample Inputs:
3 3 0
0 1 2

6 7 2
1 2 3 4 5 6

Sample Outputs:
1

3

Solution (Python):
from collections import defaultdict
(n, p, k) = [int(i) for i in input().split()]
lst = [int(i) for i in input().split()]
dic = defaultdict(lambda : 0)
for a in lst:
    m = (a ** 4 - a * k) % p
    dic[m] += 1
count = 0
for v in dic.values():
    if v != 1:
        count += v * (v - 1) / 2
print(int(count))

Solution (Python):
(n, p, k) = map(int, input().split())
pairs = {}
count = 0
for i in map(int, input().split()):
    t = (i ** 4 - k * i) % p
    if t in pairs:
        count = count + pairs[t]
        pairs[t] += 1
    else:
        pairs[t] = 1
print(count)

Solution (Python):
import sys
input = sys.stdin.readline
(n, p, k) = map(int, input().split())
A = list(map(int, input().split()))
B = [(a ** 4 - k * a) % p for a in A]
from collections import Counter
C = Counter(B)
print(sum([l * (l - 1) // 2 for l in list(C.values())]))