题解 CF1188B 【Count Pairs】
swiftc
2019-08-05 12:08:46
建议在我的博客阅读,要不然$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:
```cpp
#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;
}
```