Submission #49356980

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x) 
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;
const int MAXD = 2e4 + 10;

// ll mul(ll x, ll y, ll p) {
//     return (x * y - (ll)((long double)x / p * y) * p + p) % p;
// }

ll mul(ll x, ll y, ll p) {
    return (__int128_t)x * y % p;
}

ll ksm(ll x, ll y, ll p) {
    ll res = 1;
    while (y) {
        if (y & 1) {
            res = mul(res, x, p);
        }
        x = mul(x, x, p);
        y >>= 1;
    }
    return res;
}

int n; ll P;
ll a[MAXN], ord[MAXN];
vector<ll> vecd;

ll getord(ll x) {
    ll curp = P - 1;
    for (auto p : vecd) {
        while (curp % p == 0 && ksm(x, curp / p, P) == 1) {
            curp /= p;
            // printf("cao! curp = %lld, p = %lld \n", curp, p);
        }
    }
    return curp;
}

void solve() {
	cin >> n >> P;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    ll curp = P - 1;
    for (ll i = 2; i * i <= curp; i++) {
        if (curp % i) {
            continue;
        }
        while (curp % i == 0) {
            curp /= i;
        }
        vecd.push_back(i);
    }
    if (curp > 1) {
        vecd.push_back(curp);
    }

    for (int i = 1; i <= n; i++) {
        ord[i] = getord(a[i]);
    }

    sort(ord + 1, ord + n + 1);

    int m = 0;
    static pair<ll, int> vecord[MAXD];
    for (int i = 1; i <= n; i++) {
        if (ord[i] == ord[i - 1]) {
            vecord[m].se++;
        }
        else {
            vecord[++m] = mkp(ord[i], 1);
        }
    }

    ll ans = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (vecord[j].fi % vecord[i].fi == 0) {
                ans += 1ll * vecord[i].se * vecord[j].se;
            }
        }
    }
    printf("%lld\n", ans);
}

int main() {
	int T = 1;
	while (T--) solve();
	return 0;
}

Submission Info

Judge Result