2017多校第7场 HDU 6128 Inverse of sum 推公式或者二次剩余

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6128

题意：给你n个数，问你有多少对i,j，满足i<j，并且1/(a+a)=1/a+1/a在%p意义下。

解法：官方题解说是用二次剩余来解，但是我并不会这玩意了。在网上看到一位大佬没有二次剩余直接通过推公式做出了这题，真是神奇。http://www.cnblogs.com/bin-gege/p/7367337.html  将式子通分化简后可得（a+a+a*a）%p=0 。然后两边同时将两边乘（a-a),化简可得(a-a)%p=0。那么直接计算满足这个等式的pair的对数就可以了吗？不是。我们还要考虑到a[i]=a[j]的时候，也就是a[i]*a[i]+a[i]*a[i]+a[i]*a[i]=0modp是不满足条件的，但是我们直接计算上面那个式子会把满足这个关系的式子也算进去，所以我们需要把满足a[i]=a[j]并且3*a[i]*a[j]>0的这些对数减掉。我这个代码跑了2900多ms,所以这题还是顶二次剩余吧。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5+4;

int T,n;

LL p,a[maxn];

map<LL,int>cnt;

map<LL,int>cnt2;

inline LL quick_mul(LL a,LL n,LL m)

{

    LL ans=0;

    while(n)

    {

        if(n&1) ans=(ans+a)%m;

        a=(a+a)%m;

        n>>=1;

    }

    return ans;

}

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%lld", &n,&p);

        for(int i=1; i<=n; i++) scanf("%lld", &a[i]);

        LL ans=0;

        cnt.clear();

        cnt2.clear();

        for(int i=1; i<=n; i++){

            if(!a[i]) continue;

            if(quick_mul(3,quick_mul(a[i],a[i],p),p)) ans-=cnt2[a[i]];

            LL t = quick_mul(quick_mul(a[i],a[i],p),a[i],p);

            ans += cnt[t];

            cnt[t]++;

            cnt2[a[i]]++;

        }

        printf("%lld\n", ans);

    }

    return 0;

}