HDU 6128 Inverse of sum（同余）

http://acm.hdu.edu.cn/showproblem.php?pid=6128

题意：
有一个a数列，并且每个数都小于p，现在要求有多少对$(i,j)$满足$frac{1}{a_i+a_j} equiv frac{1}{a_i}+frac{1}{a_j} mod p$，0没有逆元。

思路：
根据同余的性质对式子进行化简，在一个同余式两边同时做加法、减法或乘法仍保持同余。

先可以化简为 $1 equiv 1+frac{a_j}{a_i}+1+frac{a_i}{a_j} mod p qquad $

然后 $a_i^2+a_j^2+a_ia_j equiv 0 mod p qquad $

最后两边乘以$a_i-a_j$，得到$a_i^3-a_j^3 equiv 0 mod p qquad$

需要特别注意的就是$a_i=a_j$的情况，因为此时乘以$a_i-a_j$就相当乘以了0，那么两边肯定就是相等，所以相等的时候就要用第二个式子来判断，这里计算三次方会爆long long，需要用快速乘法。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <map>
 4 
 5 using namespace std;
 6 typedef long long ll;
 7 const int maxn=1e5+5;
 8 
 9 int n;
10 ll p;
11 ll ans;
12 ll a[maxn];
13 
14 map<ll,int> num;
15 map<ll,int> cnt;
16 
17 ll fast_mul(ll x, ll k)
18 {
19     ll ans=0;
20     while(k)
21     {
22         if(k&1)  ans=(ans+x)%p;
23         x=(x+x)%p;
24         k>>=1;
25     }
26     return ans;
27 }
28 
29 int main()
30 {
31     //freopen("in.txt","r",stdin);
32     int T;
33     scanf("%d",&T);
34     while(T--)
35     {
36         scanf("%d%I64d",&n,&p);
37         num.clear();
38         cnt.clear();
39         ans=0;
40         for(int i=1;i<=n;i++)
41         {
42             scanf("%I64d",&a[i]);
43             if(a[i]==0)  continue;
44             if(fast_mul(fast_mul(a[i],a[i]),3))  ans-=cnt[a[i]]++;
45             ll tmp = fast_mul(fast_mul(a[i],a[i]),a[i]);
46             ans+=num[tmp]++;  //和前面的num[tmp]个数都可以组合
47         }
48         printf("%I64d
",ans);
49     }
50     return 0;
51 }