Submission #49182395

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
inline int read(){int f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}
template <class T> inline T read(){T f=1,x=0;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f;}

void getFactor(ll p,vector<ll>& fp){
    for(ll i=2;i*i<=p;i++){
        if(p%i==0){
            fp.push_back(i);
            while(p%i==0)p/=i;
        }
    }
    if(p>1)fp.push_back(p);
}

ll ksm(ll a,ll b,ll p){
    ll r = 1;
    while(b){
        if(b&1)r=(__int128_t)r*a%p;
        a=(__int128_t)a*a%p;
        b>>=1;
    }
    return r;
}

int main(){
    int n=read(); ll p=read<ll>();

    vector<ll> fp; // phi(p) 的因数
    getFactor(p-1,fp);

    map<ll,int> cnt; // 每个阶的出现次数
    for(int i=1;i<=n;i++){
        ll a=read<ll>();
        ll ord = p-1;
        for(auto f:fp){
            while(ord%f==0 && ksm(a,ord/f,p)==1)ord/=f;
        }
        cnt[ord]++;
    }

    ll ans = 0;
    for(auto [o1,c1]:cnt)for(auto [o2,c2]:cnt){
        if(o1%o2==0)ans+=(ll)c1*c2;
    }
    printf("%lld\n",ans);

    return 0;
}

Submission Info

Judge Result