CF 1188B（枚举优化）
Contents
题目链接
https://codeforces.com/contest/1188/problem/B
题意
给定 $n$ 个正整数 $a_1,a_2,…,a_n$，和一个非负整数 $k$，求满足以下条件的 $(i,j)$ 数量：
- $1\leq i < j \leq n$
- $(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$ 的值就可以了，代码略。