You are given a prime number pp, nn integers a1,a2,…,ana1,a2,…,an, and an integer kk.
Find the number of pairs of indexes (i,j)(i,j) (1≤i<j≤n1≤i<j≤n) for which (ai+aj)(a2i+a2j)≡kmodp(ai+aj)(ai2+aj2)≡kmodp.
Input
The first line contains integers n,p,kn,p,k (2≤n≤3⋅1052≤n≤3⋅105, 2≤p≤1092≤p≤109, 0≤k≤p−10≤k≤p−1). ppis guaranteed to be prime.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤p−10≤ai≤p−1). It is guaranteed that all elements are different.
Output
Output a single integer — answer to the problem.
Examples
Input 3 3 0 0 1 2 Output 1 Input 6 7 2 1 2 3 4 5 6 Output 3Note
In the first example:
(0+1)(02+12)=1≡1mod3(0+1)(02+12)=1≡1mod3.
(0+2)(02+22)=8≡2mod3(0+2)(02+22)=8≡2mod3.
(1+2)(12+22)=15≡0mod3(1+2)(12+22)=15≡0mod3.
So only 11 pair satisfies the condition.
In the second example, there are 33 such pairs: (1,5)(1,5), (2,3)(2,3), (4,6)(4,6).
题意：
找出有几组数对满足i<j，且(ai+aj)(ai^2+aj^2)≡k mod p
思路：
如果两两找O(n^2)肯定超时，所以想到需要让i与j分离，即i与j分列等式两边，这样只需扫一遍。
两边同乘(ai-aj)，制造平方差，整理后得(ai^4-aj^4)==k(ai-aj)，即ai^4-k*ai==aj^4-k*aj
排序后找相同对即可。
#include<bits/stdc++.h> #define MAX 300005 using namespace std; typedef long long ll; ll a[MAX]; int main() { int t,m,i,j; ll n,p,k; scanf("%I64d%I64d%I64d",&n,&p,&k); for(i=1;i<=n;i++){ scanf("%I64d",&a[i]); a[i]=(a[i]*a[i]%p*a[i]%p*a[i]%p-k*a[i]%p+p)%p; } sort(a+1,a+n+1); ll c=0,ans=0; for(i=2;i<=n;i++){ if(a[i-1]==a[i]){ c++; ans+=c; } else c=0; } printf("%I64d\n",ans); return 0; }
转载于:https://www.cnblogs.com/yzm10/p/11141427.html
相关资源：数据结构—成绩单生成器