求解三元组模 p 剩余系方程：高效算法与代码实现

{/"title/":/"题意/",/"description/":/"给一可重集 S SS 及质数 p pp，问能从集合中选出多少种本质不同的三元组 ( x , y , z ) ( x ≤ y ≤ z ) (x,y,z)/ (x/leq y/leq z)(x,y,z) (x≤y≤z) 使得 x y z ≡ 1 ( m o d p ) xyz/equiv 1/pmod pxyz≡1(modp)？∣ S ∣ ≤ 2333 , p ≤ 2 30 |S|/leq 2333,p/leq 2^{30}∣S∣≤2333,p≤2//n30//n//n70% 解//n保证 x < p ∣ x ∈ S x<p|x/in Sx<p∣x∈S。首先排序所有数并预处理出其逆元。接着枚举 x , y ( x ≤ y ) x,y(x/leq y)x,y(x≤y)，算出 z = x − 1 y − 1 z=x^{-1}y^{-1}z=x//n−1//ny//n−1//n ，检查是否 y ≤ z y/leq zy≤z 以及是否 z ∈ S z/in Sz∈S（二分）。注意处理有数字相等的情况。//n//n100% 解//n排序时优先根据 m o d    p /mod pmodp 结果排序，并将所有数字去重后的结果另外存储一份。仍然枚举 x , y ( x ≤ y ) x,y(x/leq y)x,y(x≤y)，算出 z zz，统计与 z zz 在同一剩余系下的数字个数。同样注意处理有数字相等的情况。//n//n代码：//n//n#include<bits/stdc++.h>//nusing namespace std;//nint getint(){//n/tint ans=0,f=1;//n/tchar c=getchar();//n/twhile(c<'0'||c>'9'){//n/t/tif(c=='-')f=-1;//n/t/tc=getchar();//n/t}//n/twhile(c>='0'&&c<='9'){//n/t/tans=ans10+c-'0';//n/t/tc=getchar();//n/t}//n/treturn ansf;//n}//nint p;//n//nbool cmp(int a,int b){//n/tif(a%p!=b%p)return a%p<b%p;//n/treturn a<b;//n}//nbool cmp2(int a,int b){//n/treturn a%p<b%p;//n}//n//ninline int qpow(int x,int y,int z){//n/tint ans=1;//n/twhile(y){//n/t/tif(y&1)ans=ans1llx%z;//n/t/tx=x1llx%z;//n/t/ty>>=1;//n/t}//n/treturn ans;//n}//nint a[3000];//nint inv[3000];//nint uniq[3000];//n//nint main(){//n/tint n=getint();//n/tp=getint();//n/tint sqrtn=sqrt(n);//n/tfor(int i=0;i<n;i++){//n/t/ta[i]=getint();//n/t}//n/tsort(a,a+n,cmp);//n/tmemcpy(uniq,a,sizeof(uniq));//n/tint r_=unique(uniq,uniq+n)-uniq;//n/tfor(int i=0;i<n;i++){//n/t/tinv[i]=qpow(a[i],p-2,p);//n/t}//n/tint ans=0;//n/t//a[i]<a[j]<=a[k]//n/tfor(int i=0;i<n;i++){//n/t/tif(a[i]==0)continue;//n/t/tif(i&&a[i-1]==a[i])continue;//n/t/tfor(int j=i+1;j<n;j++){//n/t/t/tif(j&&a[j-1]==a[j])continue;//n/t/t/tif(a[i]==a[j])continue;//n/t/t/tint ak=inv[i]1llinv[j]%p;//n/t/t/t//cout<</">> ? /"<<a[i]/" /"<<a[j]/" /"<<ak<<endl;//n/t/t/tif(ak%p<a[j]%p)continue;//n/t/t/tif(ak%p==a[j]%p){//n/t/t/t/tans+=(a[j+1]==a[j]);//n/t/t/t/t//cout<</"> /"<<ans<<endl;//n/t/t/t/tans+=upper_bound(uniq,uniq+r_,ak,cmp2)//n/t/t/t/t/t-upper_bound(uniq,uniq+r_,a[j],cmp);//n/t/t/t/t//cout<</"> /"<<ans<<endl;//n/t/t/t}else{//n/t/t/t/tans+=upper_bound(uniq,uniq+r_,ak,cmp2)//n/t/t/t/t/t-lower_bound(uniq,uniq+r_,ak,cmp2);//n/t/t/t}//n/t/t}//n/t}//n/t//a[i]=a[j]<=a[k]//n/tfor(int i=0;i<n-1;i++){//n/t/tif(a[i]!=a[i+1])continue;//n/t/tif(i&&a[i-1]==a[i])continue;//n/t/tif(a[i]==0)continue;//n/t/tint ak=inv[i]1llinv[i]%p;//n/t/tif(ak%p<a[i]%p)continue;//n/t/tif(ak%p==a[i]%p){//n/t/t/tans+=(a[i+2]==a[i]);//n/t/t/t//cout<</"> /"<<ans<<endl;//n/t/t/tans+=upper_bound(uniq,uniq+r_,ak,cmp2)//n/t/t/t/t-upper_bound(uniq,uniq+r_,a[i],cmp);//n/t/t/t//cout<</"> /"<<ans<<endl;//n/t/t}else{//n/t/t/tans+=upper_bound(uniq,uniq+r_,ak,cmp2)//n/t/t/t/t-lower_bound(uniq,uniq+r_,ak,cmp2);//n/t/t}//n/t}//n/tprintf(/'%d//n/',ans);//n/treturn 0;//n}//n//n//n这份代码中：//nif(ak%p<a[j]%p)continue;//n/t/t/tif(ak%p==a[j]%p){//n/t/t/t/tans+=(a[j+1]==a[j]);//n/t/t/t/t//cout<</"> /"<<ans<<endl;//n/t/t/t/tans+=upper_bound(uniq,uniq+r_,ak,cmp2)//n/t/t/t/t/t-upper_bound(uniq,uniq+r_,a[j],cmp);//n/t/t/t/t//cout<</"> /"<<ans<<endl;//n/t/t/t}else{//n/t/t/t/tans+=upper_bound(uniq,uniq+r_,ak,cmp2)//n/t/t/t/t/t-lower_bound(uniq,uniq+r_,ak,cmp2);//n/t/t/t}//n//n是什么意思内容：这段代码的作用是统计满足条件的三元组的数量。具体的流程如下：//n1. 首先判断ak除以p的余数是否小于a[j]除以p的余数，如果是，则跳过当前循环。//n2. 如果ak除以p的余数等于a[j]除以p的余数，说明ak和a[j]在同一个剩余系下。此时需要判断a[j+1]是否等于a[j]，如果是，说明ak和a[j]都与a[j+1]在同一个剩余系下，将ans加1。然后使用upper_bound函数找到在uniq数组中大于ak的第一个数的位置，再使用upper_bound函数找到在uniq数组中大于a[j]的第一个数的位置，将两者相减，得到ak在uniq数组中的个数，将ans加上这个个数。//n3. 如果ak除以p的余数不等于a[j]除以p的余数，说明ak和a[j]在不同的剩余系下。此时使用upper_bound函数找到在uniq数组中大于ak的第一个数的位置，再使用lower_bound函数找到在uniq数组中小于等于ak的最后一个数的位置，将两者相减，得到ak在uniq数组中的个数，将ans加上这个个数。//n//n综上所述，这段代码的作用是统计满足条件的三元组的数量，并将结果保存在变量ans中。