CF2095E.Pair Count

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

请你求出满足条件 $(a_i \oplus a_j)(a_i^2 \oplus a_j^2) \equiv k \pmod{p}$ 的下标对 $(i, j)$ 的数量（$1 \le i < j \le n$）。

其中 $\oplus$ 表示按位异或运算。

第一行包含三个整数 $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$）。保证所有元素互不相同。

输出一个整数，表示满足条件的下标对数量。

在第一个样例中：

$(0\oplus1)(0^2 \oplus 1^2) = 1 \equiv 1 \pmod{3}$。

$(0\oplus2)(0^2 \oplus 2^2) = 8 \equiv 2 \pmod{3}$。

$(1\oplus2)(1^2 \oplus 2^2) = 15 \equiv 0 \pmod{3}$。

因此只有 $1$ 对满足条件。

在第二个样例中，有 $3$ 对满足条件，分别是 $(1, 5)$、$(1, 6)$、$(3, 6)$。

由 ChatGPT 4.1 翻译