description：

给出一个长度为 n n n 的整数序列， a 1 , a 2 , … , a n a1,a2,…,an a1,a2,…,an，序列中的数互不相同 给出质数 p p p 请问有多少序列中的有序数对 ( x , y ) (x,y) (x,y)满足

( x 2 + y ) 2 ≡ ( x 2 − y ) 2 + 1 ( m o d p ) (x^2 + y)^2 ≡ (x^2 − y)^2 + 1 (mod p) (x2+y)2≡(x2−y)2+1(modp)

solution：

原式为：
( x 2 + y ) 2 ≡ ( x 2 − y ) 2 + 1 ( m o d p ) (x^2 + y)^2 ≡ (x^2 − y)^2 + 1 (modp) (x2+y)2≡(x2−y)2+1(modp)

两边拆开：

x 2 + 2 x 2 y + y 2 ≡ x 2 − 2 x 2 y + y 2 + 1 ( m o d p ) x^2+2x^2y+y^2 ≡ x^2-2x^2y+y^2 + 1 (modp) x2+2x2y+y2≡x2−2x2y+y2+1(modp)

化简：

4 x 2 y ≡ 1 ( m o d p ) 4x^2y ≡ 1 (mod p) 4x2y≡1(modp)

于是就是找 4 x 2 4x^2 4x2的逆元y在不在序列里了。

弄个map统计一下就可以了。

注意要考虑重复的数

第一种：（mine）

#include<cstdio>
#include<map>
using namespace std;
map<long long,long long>m;
long long a[500005],b[500005];
void exgcd(long long a,long long p,long long &d,long long &x,long long &y)
{
	if(p==0)
	{
		d=a;
		x=1;
		y=0;
	}
	else
	{
		exgcd(p,a%p,d,y,x);
		y-=x*(a/p); 
	}
}
long long inv(long long a,long long p)
{
	long long d,x,y;
	exgcd(a,p,d,x,y);
	if(d==1)
	{
		return (x+p)%p;
	}
	else
	{
		return -1;
	}
}
int main()
{
	long long n,p,x;
	scanf("%lld%lld",&n,&p);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		b[i]=x;
		m[(((4*x)%p)*x)%p]++;
		a[i]=(((4*x)%p)*x)%p;
	}
	long long ans=0;
	m[0]=0;
	for(long long i=1;i<=n;i++)
	{
		long long tmp=inv(b[i],p);
		if(tmp!=-1)
		ans+=m[tmp];
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]*b[i]%p==1)
		ans--;
	}
	printf("%lld\n",ans);
	return 0;
}

第二种：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#define maxn 1100000

using namespace std;

int n,p,a[maxn];
long long ans;

map<int,int> mp;

int rev(int x)
{
    int ans=1;
    int q=p-2;
    while(q)
    {
        if(q&1)
            ans=(long long)ans*x%p;
        x=(long long)x*x%p;
        q>>=1;
    }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        mp[((long long)a[i]*a[i]%p)*4%p]++;
    mp[0]=0;
    for(int i=1;i<=n;i++)
        ans+=mp[rev(a[i])];
    for(int i=1;i<=n;i++)
        if(((((long long)a[i]*a[i]%p)*4%p)*a[i])%p==1)
            ans--;
    printf("%lld\n",ans);
    return 0;
}