题解 CF1188B 【Count Pairs】

· · 题解

建议在我的博客阅读,要不然markdown可能会炸 QAQ

看这个式子：(a_i+a_j)*(a_i^2+a_j^2)≡k\ mod\ p

大家都知道平方差公式吧:

(a+b)*(a-b)=a^2-b^2

那么把这个式子乘上一个(a_i-a_j),得：

(a_i^2+a_j^2)*(a_i^2-a_j^2)≡k*(a_i-a_j)\ mod \ p

即：

(a_i^4-a_j^4)≡k*(a_i-a_j)\ mod \ p

把k*a_i移到等式左边，a_j^4移到等式右边，就变成了：

a_i^4-a_i*k≡a_j^4-a_j*k\ mod \ p

就可以用map O(n\ log\ n)判断了

时间复杂度还不够低？

请出tr1::unordered_map，这是一个时间复杂度为O(1)的map，使用方法见我的代码

code:

#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define int long long
using namespace std;
int n,p,k,a[300001],b[300001];
tr1::unordered_map<int,int>ma;
int qpow(int a,int b){
    if(b==0)return 1;
    int tmp=qpow(a,b/2);
    return b%2?tmp*tmp%p*a%p:tmp*tmp%p;
}
int ans=0;
main(){
    scanf("%lld%lld%lld",&n,&p,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        b[i]=(qpow(a[i],4)-k*a[i]%p)%p;
        while(b[i]<0)b[i]=(b[i]+p)%p;
    }
    for(int i=1;i<=n;i++){
        ans+=ma[b[i]];
        ma[b[i]]++;
    }
    printf("%lld\n",ans);
    return 0;
}