1189E.Count Pairs_牛客博客

1189E.Count Pairs

$Description$
You are given a prime number $p$ , $n$ different integers $a1,a2,…,an,$ and an integer $k$ .
Find the number of pairs of indexes $(i,j) (1≤i<j≤n)$ for which $(a_i + a_j)(a_i^2 + a_j^2) \equiv k \; mod \;p$ .

$Solution$
因为 $a_i!=a_j$ 所以 $(a_i-a_j)(a_i + a_j)(a_i^2 + a_j^2) \equiv k(a_i-a_j) \; mod \; p$ 整理得 $a_i^{4}-k \cdot a_i \equiv a_j^{4}-k \cdot a_j \; mod \; p$ . 又因为 $gcd(p,a_i-a_j)=1$ 所以上述式子与原式等价.

$Code$

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define itn int
using namespace std;
const int N=1e6;
const long long mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");}
template <typename it>
string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;}
template <typename it>int o(it a){cout<<a<<endl;return 0;}
ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;}
ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;}
int n,p,k;
map<int,int>dp;
int main(){
    //freopen("in.txt","r",stdin);
    ll ans=0;
    cin>>n>>p>>k;
    for(int i=1;i<=n;i++){
        int u;
        sc("%d",&u);
        int x=1ll*u*((1ll*u*u%p*u%p-k+p)%p)%p;
        ans+=dp[x]++;
    }
    o(ans);
}