Codeforces Round #572 (Div. 1)

B.Count Pairs

$\mathtt{Difficulty}$=$\mathtt{2300}$
二话不说，先推一波式子
$(a_i+a_j)(a_i^2+a_j^2)\equiv k\pmod{p}$
$\Rightarrow (a_i+a_j)(a_i-a_j)(a_i^2+a_j^2)\equiv k(a_i-a_j)\pmod{p}$
$\Rightarrow a_i^4-a_j^4\equiv k(a_i-a_j)\pmod{p}$
$\Rightarrow a_i^4-ka_i\equiv a_j^4-ka_j\pmod{p}$
推到这里就够了
我们发觉可以直接用 map 记录第 $i$ 个元素的 $a_i^4-ka_i$ 对 $p$ 取模的值
然后直接算答案即可
代码不难写出

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
#define int long long
int N,K,MOD,A[300001];
map< int,int >Map;
signed main(void)
{
	BetterIO;
	register int i,Ans=0;cin>>N>>MOD>>K;
	for(i=1;i<=N;i++)
	{
		register int Remainder;cin>>A[i],A[i]%=MOD;
		Remainder=A[i]*A[i]%MOD*A[i]%MOD*A[i]%MOD-K*A[i]%MOD+MOD;
		Ans+=Map[Remainder%MOD];
		Map[Remainder%MOD]++;
	}
	cout<<Ans<<endl;
	return 0;
}