CF 572 B Count Pairs

大致题意:

给n,p,k,p是质数,还有n个数 a[1],a[2],…,a[n].求有多少对(i,j)满足(a[i]+a[j])(a[i]^2+a[j]^2)%p==k.(2<=n<=3e5 2<=p<=1e9 0<=k<=p-1)

解题思路:

(a[i]+a[j])(a[i]^2+a[j]^2) = (a[i]^4-a[j]^4)/(a[i]-a[j]),化简得 ((a[i]^4-k×a[i])-(a[j]^4-k×a[j]))%p==k,于是只要把(a[i]^4-k×a[i])%p 的余数算出来就知道答案了.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int a[N];
map<int,int>mp;
int main(){
	int n,p,k;
	scanf("%d%d%d",&n,&p,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		a[i]=(1ll*a[i]*a[i]%p*a[i]%p*a[i]%p-1ll*k*a[i]%p+p)%p;
		mp[a[i]]++;
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans+=mp[a[i]]-1;
	}
	printf("%lld\n",ans/2);
}