CF1188B.Count Pairs

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 \lt j \le n$) for which $(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$.

给你一个质数 $p$、$n$ 个整数 $a_1, a_2, \ldots, a_n$ 以及一个整数 $k$。

请你找出满足 $(a_i + a_j)(a_i^2 + a_j^2) \equiv k \bmod p$ 的下标对 $(i, j)$（其中 $1 \le i \lt j \le n$）的个数。

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.

第一行包含整数 $n, p, k$（$2 \le n \le 3 \cdot 10^5$，$2 \le p \le 10^9$，$0 \le k \le p-1$）。保证 $p$ 是质数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le p-1$）。保证所有元素互不相同。

Output a single integer — answer to the problem.

输出一个整数——问题的答案。

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)$.

在第一个例子中：

$(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$。

因此，仅有 $1$ 对满足条件。

在第二个例子中，共有 $3$ 对满足条件：$(1, 5)$、$(2, 3)$、$(4, 6)$。