计数三元组：满足模 p 同余式的本质不同三元组数量

给定一个可重复集合 S 和一个质数 p，求解能从集合中选出多少种本质不同的三元组 (x, y, z) (x ≤ y ≤ z)，满足 x * y * z ≡ 1 (mod p)。|S| ≤ 2333, p ≤ 2^30\ \ 70% 解\ 保证 x < p | x ∈ S。首先排序所有数并预处理出其逆元。接着枚举 x, y (x ≤ y)，算出 z = x^-1 * y^-1，检查是否 y ≤ z 以及是否 z ∈ S（二分）。注意处理有数字相等的情况。\ \ 100% 解\ 排序时优先根据 mod p 结果排序，并将所有数字去重后的结果另外存储一份。仍然枚举 x, y (x ≤ y)，算出 z，统计与 z 在同一剩余系下的数字个数。同样注意处理有数字相等的情况。\ \ 代码：\ \ #include<bits/stdc++.h>\ using namespace std;\ int getint(){\ int ans=0,f=1;\ char c=getchar();\ while(c<'0'||c>'9'){\ if(c=='-')f=-1;\ c=getchar();\ }\ while(c>='0'&&c<='9'){\ ans=ans10+c-'0';\ c=getchar();\ }\ return ansf;\ }\ int p;\ \ bool cmp(int a,int b){\ if(a%p!=b%p)return a%p<b%p;\ return a<b;\ }\ bool cmp2(int a,int b){\ return a%p<b%p;\ }\ \ inline int qpow(int x,int y,int z){\ int ans=1;\ while(y){\ if(y&1)ans=ans1llx%z;\ x=x1llx%z;\ y>>=1;\ }\ return ans;\ }\ int a[3000];\ int inv[3000];\ int uniq[3000];\ \ int main(){\ int n=getint();\ p=getint();\ int sqrtn=sqrt(n);\ for(int i=0;i<n;i++){\ a[i]=getint();\ }\ sort(a,a+n,cmp);\ memcpy(uniq,a,sizeof(uniq));\ int r_=unique(uniq,uniq+n)-uniq;\ for(int i=0;i<n;i++){\ inv[i]=qpow(a[i],p-2,p);\ }\ int ans=0;\ //a[i]<a[j]<=a[k]\ for(int i=0;i<n;i++){\ if(a[i]==0)continue;\ if(i&&a[i-1]==a[i])continue;\ for(int j=i+1;j<n;j++){\ if(j&&a[j-1]==a[j])continue;\ if(a[i]==a[j])continue;\ int ak=inv[i]1llinv[j]%p;\ //cout<<'>> ? '<<a[i]<<' '<<a[j]<<' '<<ak<<endl;\ if(ak%p<a[j]%p)continue;\ if(ak%p==a[j]%p){\ ans+=(a[j+1]==a[j]);\ //cout<<'> '<<ans<<endl;\ ans+=upper_bound(uniq,uniq+r_,ak,cmp2)\ -upper_bound(uniq,uniq+r_,a[j],cmp);\ //cout<<'> '<<ans<<endl;\ }else{\ ans+=upper_bound(uniq,uniq+r_,ak,cmp2)\ -lower_bound(uniq,uniq+r_,ak,cmp2);\ }\ }\ }\ //a[i]=a[j]<=a[k]\ for(int i=0;i<n-1;i++){\ if(a[i]!=a[i+1])continue;\ if(i&&a[i-1]==a[i])continue;\ if(a[i]==0)continue;\ int ak=inv[i]1llinv[i]%p;\ if(ak%p<a[i]%p)continue;\ if(ak%p==a[i]%p){\ ans+=(a[i+2]==a[i]);\ //cout<<'> '<<ans<<endl;\ ans+=upper_bound(uniq,uniq+r_,ak,cmp2)\ -upper_bound(uniq,uniq+r_,a[i],cmp);\ //cout<<'> '<<ans<<endl;\ }else{\ ans+=upper_bound(uniq,uniq+r_,ak,cmp2)\ -lower_bound(uniq,uniq+r_,ak,cmp2);\ }\ }\ printf('%d\n',ans);\ return 0;\ }\ \ 这份代码中：\ if(ak%p<a[j]%p)continue;\ if(ak%p==a[j]%p){\ ans+=(a[j+1]==a[j]);\ //cout<<'> '<<ans<<endl;\ ans+=upper_bound(uniq,uniq+r_,ak,cmp2)\ -upper_bound(uniq,uniq+r_,a[j],cmp);\ //cout<<'> '<<ans<<endl;\ }else{\ ans+=upper_bound(uniq,uniq+r_,ak,cmp2)\ -lower_bound(uniq,uniq+r_,ak,cmp2);\ }\ \ 是什么意思，请你解释这么做的理由内容：这部分代码是用来统计与z在同一剩余系下的数字个数。\ \ 首先，对于给定的x和y，计算z = x^(-1) * y^(-1) (mod p)。其中，x^(-1)和y^(-1)分别表示x和y在模p下的逆元。\ \ 接下来，分三种情况讨论：\ \

如果ak % p < a[j] % p，说明ak在剩余系中的值小于a[j]，因此不满足y <= z的条件，直接跳过。\ \
如果ak % p == a[j] % p，说明ak和a[j]在同一剩余系中。此时，需要判断ak是否与a[j]相等。如果ak和a[j]相等，则需要额外统计a[j+1]是否与a[j]相等，然后统计在uniq数组中，ak在剩余系中的数字个数（通过upper_bound和lower_bound函数实现）。\ \
如果ak % p > a[j] % p，说明ak在剩余系中的值大于a[j]，直接统计在uniq数组中，ak在剩余系中的数字个数（通过upper_bound和lower_bound函数实现）。\ \ 最后，将统计结果累加到答案ans中。