感觉并不是特别难的题。
首先是一个简单的推式子,有原式:
\[(a_i+a_j) \times ({a_i}^2+{a_j}^2) \equiv k \mod p
\]
如何针对 \(a_i+a_j\) 进行有效处理呢?不难想到平方差公式:
\[(a_i+a_j) \times (a_i-a_j) \times ({a_i}^2+{a_j}^2) \equiv k \times (a_i-a_j) \mod p
\]
合并左式一二项,同时拆右式括号:
\[({a_i}^2-{a_j}^2) \times ({a_i}^2+{a_j}^2) \equiv k \times a_i - k \times a_j \mod p
\]
我们发现可以再针对 \({a_i}^2\) 和 \({a_j}^2\) 使用平方差公式,则有:
\[{a_i}^4 - {a_j}^4 \equiv k \times a_i - k \times a_j \mod p
\]
移项得:
\[{a_i}^4 - k \times a_i \equiv {a_j}^4 - k \times a_j \mod p
\]
也就是说,针对每一个 \(a_i\),我们只需要注意 \({a_i}^4 - k \times a_i\) 即可。可以考虑使用 unordered_map
维护并记录方案数。
// Problem: Count Pairs
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1188B
// Memory Limit: 250 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define int long long
#define ok puts("YES")
#define no puts("NO")
#define debug puts("Tomotake_Yoshino_my_wife")
#define clean fflush(stdout)
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
const int maxn=3e5+5;
int binpow(int a,int b,int mod){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int n,p,k;
int res,ans;
int a[maxn];
unordered_map<int,int> mp;
inline void init(){
n=read();p=read();k=read();
for(register int i=1;i<=n;++i) a[i]=read();
}
signed main(){
init();
for(register int i=1;i<=n;++i){
res=binpow(a[i],4,p)-k*a[i]%p;res=(res+p)%p;
ans+=mp[res];ans%=p;mp[res]++;mp[res]%=p;
}
printf("%lld",ans);
}