Codeforces Count Pairs

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

$ (a_i+a_j)(a_i^2+a_j^2)\equiv k(mod p) $

$ (a_i^4-a_j^4)\equiv (a_i-a_j)k(mod p) $

$ a_i^4-a_ik\equiv a_j^4-a_jk(mod p) $

모든 $ a_i $에 대하여 $ a_i^4-a_ik(mod p) $ 를 저장해 둔 후, 같은 값을 가지는 $ a_i $가 2개 이상이면 combination 하면 되는 수학문제이다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=300005;
typedef long long ll;
map<ll,ll> vst;
ll n,p,k;
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>p>>k;
	for(int i=1;i<=n;i++){
		ll x; cin>>x;
		ll rem=(x*(x*(x*x%p)%p+p-k))%p;
		vst[rem]++;
	}
	ll ans=0;
	for(auto it=vst.begin();it!=vst.end();++it){
		if(it->second>1){
			ans+=((it->second)*(it->second-1))/2;
		}
	}
	cout<<ans;
	return 0;
}