传送门
题意：
存在一个长度为n的非负数列a,满足条件ai<aj<p 。求存在多少对(i,j)满足
思路：
题目中已经说了0没有逆元，即碰到0 continue即可。 先对题目中的式子进行化简，获得
再化简，得：
两边同时乘以ai-aj，得：
推到这里就是整数上的运算了，做法是建立两个map，一个存余数出现的次数，一个存ai出现的次数。
这样对每个ai遍历时只修改了当前余数和ai对应的map中的值，而不用O(n^2)地遍历，有效降低了复杂度。
注意一点，由（2）式变到（3）式的时候，如果ai==aj的话，式子式恒成立的，所以要加个判断，当ai==aj的时候，（2）式左边变成了3*ai^2,如果左边%p！=0,说明（2）式不成立，这时应该减去ai对最后结果的贡献。
#include<bits/stdc++.h> using namespace std; #define LL long long #define MAXN 100100 LL a[MAXN]; map<LL,int> tongyu;///记录同余的个数 map<LL,int> num;///记录每个数据出现的次数 LL multi(LL a,LL b,LL p){ LL ret=0; while(b){ if(b&1) ret=(ret+a)%p; b>>=1; a=(a+a)%p; } return ret; } int main(){ int T,n; LL p,ans; scanf("%d",&T); while(T--){ scanf("%d %lld",&n,&p); num.clear(); tongyu.clear(); ans=0; for(int i=0;i<n;i++){ scanf("%lld",&a[i]); if(a[i]==0) continue; if(multi(multi(a[i],a[i],p),3,p))///a[i]和a[j]相等时不满足%p=0 ans-=num[a[i]]; LL val=multi(multi(a[i],a[i],p),a[i],p); ans+=tongyu[val]++;///前面出现过的余数相同的个数，贡献完自加 num[a[i]]++;///这个数出现的次数 } printf("%lld\n",ans); } }
