Inverse of sum

题目链接

题意

给一个数列$a$,问有多少对$i,j$满足

$$\frac{1}{a_{i} + a_{j} } \equiv \frac{1}{a_{i} } + \frac{1}{a_{j} } mod p$$

思路

$$\frac{1}{a_{i} + a_{j} } \equiv \frac{1}{a_{i} } + \frac{1}{a_{j} } mod p$$ $$\frac{1}{a_{i} + a_{j} } \equiv \frac{a_{i} + a_{j} }{a_{i} a_{j}} mod p$$ $${(a_{i} + a_{j})}^{2} \equiv a_{i} a_{j} mod p$$ $${a_{i} }^{2} + {a_{j} }^{2} + a_{i} a_{j} \equiv 0 mod p$$ $$(a_{i} - a_{j})({a_{i} }^{2} + {a_{j} }^{2} + a_{i} a_{j}) \equiv 0 mod p$$ $${a_{i} }^{3} - {a_{j} }^{3} \equiv 0 mod p$$

这样我们就找到了满足这个条件的$i$与$j$的关系，注意去掉一些$a_{i} = a_{j}$的情况。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
ll mod;
ll mult(ll a, ll b)
{
	ll ans = 0;
	while (b)
	{
		if (b & 1)
			ans = (ans + a) % mod;
		a = (a + a) % mod;
		b >>= 1;
	}
	return ans;
}

ll Pow(ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1)
			ans = mult(ans, a);
		a = mult(a, a);
		b >>= 1;
	}
	return ans;
}

template<class T>
void read(T& ret)
{
	ret = 0;
	char c;
	while ((c = getchar()) > '9' || c < '0');
	while (c >= '0' && c <= '9')
	{
		ret = ret * 10 + c - '0';
		c = getchar();
	}
}
const int maxn=1e5+100;
ll a[maxn];
map <ll,int> mp1,mp2;
int main(){
	int T;
	read(T);
	while (T--)
	{
		int n;
		read(n);
		read(mod);
		for(int i=1;i<=n;i++){
			read(a[i]);
		}
		mp1.clear(); mp2.clear();
		ll ans=0;
		for(int i=1;i<=n;i++){
			if(a[i]==0) continue;
			ll tmp=mult(mult(a[i],a[i]),a[i]);
			ans+=mp2[tmp];
			if(mp1[a[i]]!=0){
				ll tmp2=mult(a[i],a[i])*3%mod;
				if(tmp2!=0){
					ans-=mp1[a[i]];
				}
			}
			mp1[a[i]]++;
			mp2[tmp]++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}