题目链接

https://codeforces.com/contest/1188/problem/B

题意

给定 $n$ 个正整数 $a_1,a_2,…,a_n$,和一个非负整数 $k$,求满足以下条件的 $(i,j)$ 数量:

  1. $1\leq i < j \leq n$
  2. $(a_i+a_j)(a_i^2+a_j^2) \equiv k \text{ mod } p$

其中,$2 \leq n \leq 3 \times 10^5, 2 \leq p \leq 10^9, 0\leq k \leq p-1, p$ 是质数。

题解

一般这种求 $(i,j)$ 的数量,一个常规操作是构造出 $f(i) = g(j)$,然后在遍历过程中维护一个 cnt,直接加到 ans 上。

所以我们想个办法 把 $i,j$ 分到两边

$(a_i+a_j)(a_i^2+a_j^2) = k$,两边同乘 $(a_i-a_j)$,有 $a_i^4-a_j^4 = k(a_i-a_j)$,移项得到

$$a_i^4 - ka_i = a_j^4-ka_j$$

所以维护一个 cnt 来记录 $a_i^4 - ka_i$ 的值就可以了,代码略。