数学--数论--HDU 6128 Inverse of sum （公式推导论）

Description

给nn个小于pp的非负整数a1,…,na1,…,n，问有多少对(i,j)(1≤i<j≤n)(i,j)(1≤i<j≤n)模pp在意义下满足1ai+aj≡1ai+1aj1ai+aj≡1ai+1aj，即这两个数的和的逆元等于这两个数的逆元的和，注意0没有逆元

Input

第一行一整数TT表示用例组数，每组用例首先输入一整数nn表示序列长度和一素数pp表示模数，之后输入nn个非负整数a1,…,n(1≤T≤5,1≤n≤2×105,2≤p≤1018,0≤a1,…,n<p)a1,…,n(1≤T≤5,1≤n≤2×105,2≤p≤1018,0≤a1,…,n<p)

Output

输出满足条件的(i,j)(1≤i<j≤n)(i,j)(1≤i<j≤n)对数

Sample Input

2

5 7

1 2 3 4 5

6 7

1 2 3 4 5 6

Sample Output

4

6

最后我明白了个道理，当底数过大时，不能用普通乘法，更不不能用快速幂，因为乘一遍就爆了。于是酿成惨剧！

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define _m(a, p) make_pair(a, p)

map<ll, ll> mp;

map<ll, ll> mm;

ll mod;

long long ksc(long long a, long long b, long long mod)

{

    long long ans = 0;

    for (; b; b >>= 1){

        if (b & 1)

            ans = (ans + a) % mod;

            a = (a + a) % mod; //（计算机加法比乘法快，a+a比a*2快）

    }

    return ans;

}

int main()

{

    int t, n;

    scanf("%d", &t);

    while (t--)

    {

        ll cnt = 0;

        mp.clear();

        mm.clear();

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

        for (int i = 0; i < n; i++)

        {

            ll a;

            scanf("%lld", &a);

            if (!a)

                continue;

            mm[a]++;

            ll ans = ksc(ksc(a, a, mod), a, mod);

            mp[ans]++;

        }

        for (auto p : mp)

        {

            ll cc = p.second;

            cnt += cc * (cc - 1) / 2;

        }

        if (mod != 3)

            for (auto m : mm)

            {

                ll n = m.second;

                cnt -= n * (n - 1) / 2;

            }

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

    }

    return 0;

}

巴特西

数学--数论--HDU 6128 Inverse of sum （公式推导论）

最新文章

热门文章