Codeforces 1188B Count Pairs

矫情吗；* 2021-12-17 00:19 122阅读 0赞

[Count Pairs][]

这么sb的题居然写了这么久。。

两边同时乘以(ai - aj)， 化简一下就好了。

#include<bits/stdc++.h>
    #define LL long long
    #define LD long double
    #define ull unsigned long long
    #define fi first
    #define se second
    #define mk make_pair
    #define PLL pair<LL, LL>
    #define PLI pair<LL, int>
    #define PII pair<int, int>
    #define SZ(x) ((int)x.size())
    #define ALL(x) (x).begin(), (x).end()
    #define fio ios::sync_with_stdio(false); cin.tie(0);
     
    using namespace std;
     
    const int N = 3e5 + 7;
    const int inf = 0x3f3f3f3f;
    const LL INF = 0x3f3f3f3f3f3f3f3f;
    const int mod = 998244353;
    const double eps = 1e-8;
    const double PI = acos(-1);
     
    template<class T, class S> inline void add(T &a, S b) {a += b; if(a >= mod) a -= mod;}
    template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}
    template<class T, class S> inline bool chkmax(T &a, S b) {
        return a < b ? a = b, true : false;}
    template<class T, class S> inline bool chkmin(T &a, S b) {
        return a > b ? a = b, true : false;}
     
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     
    LL n, p, k;
    LL a[N];
    LL hs[N], tot;
    LL c[N];
    map<LL, LL> Map;
     
    int main() {
        scanf("%lld%lld%lld", &n, &p, &k);
        for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        for(int i = 1; i <= n; i++) {
            hs[++tot] = a[i];
        }
        sort(hs + 1, hs + 1 + tot);
        tot = unique(hs + 1, hs + 1 + tot) - hs - 1;
        for(int i = 1; i <= n; i++) {
            c[lower_bound(hs + 1, hs + 1 + tot, a[i]) - hs]++;
        }
        LL ans = 0;
        for(int i = 1; i <= tot; i++) {
            LL v = hs[i];
            LL tmp = (v * v % p * v % p * v % p - k * v % p + p) % p;
            ans += Map[tmp];
            LL tmp2 = 2 * v % p * ((v * v % p + v * v % p) % p) % p;
            if(tmp2 == k) ans += c[i] * (c[i] - 1) / 2;
            Map[tmp] += c[i];
        }
        printf("%lld\n", ans);
        return 0;
    }
     
    /*
    */

转载于:https://www.cnblogs.com/CJLHY/p/11142565.html

[Count Pairs]: https://codeforces.com/problemset/problem/1188/B