提出 #49129894

---

ソースコード 拡げる

// Problem: AtCoder - AtCoder Beginner Contest 335 (Sponsored by Mynavi) G - Discrete Logarithm Problems
// Url: https://atcoder.jp/contests/abc335/tasks/abc335_g
// T/M Limit: 5000ms 1024MB
// Time: 2024-01-06 21:02:24
// Author: ShaoJia

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define rep(Ii,Jj,Kk) for(int Ii=(Jj),Ii##_=(Kk);Ii<=Ii##_;Ii++)
#define per(Ii,Jj,Kk) for(int Ii=(Jj),Ii##_=(Kk);Ii>=Ii##_;Ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double db;
#define fir first
#define sec second
#define pb push_back
#define eb emplace_back
#define siz(Aa) ((int)(Aa).size())
#define all(Aa) (Aa).begin(),(Aa).end()
#define ckmx(Aa,Bb) (Aa=max(Aa,Bb))
#define ckmn(Aa,Bb) (Aa=min(Aa,Bb))
#define int ll
const int N=200010,V=4e6;
int n,P,a[N];
vector<int> v;
int fpw(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=__int128(res)*x%P;
		}
		x=__int128(x)*x%P;
		y>>=1;
	}
	return res;
}
map<int,int> f;
signed main(){ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>P;
    rep(i,1,V) if((P-1)%i==0){
    	f[i]=0;
    	f[(P-1)/i]=0;
    }
    int x=P-1;
    rep(i,2,V) if(x%i==0){
    	v.emplace_back(i);
    	do{
    		x/=i;
    	}while(x%i==0);
    }
    if(x>1) v.emplace_back(x);
    rep(i,1,n){
    	cin>>x;
    	int y=P-1;
    	for(int j:v){
    		while(y%j==0 && fpw(x,y/j)==1){
    			y/=j;
    		}
    	}
    	a[i]=y;
    	f[y]++;
    }
    // rep(i,1,n) cout<<a[i]<<" \n"[i==i_];
    for(int i:v){
    	for(const auto&[id,val]:f){
    		if(id*i>=P) break;
    		if(f.count(i*id)) f[i*id]+=val;
    	}
    }
    int ans=0;
    rep(i,1,n) ans+=f[a[i]];
    cout<<ans<<"\n";
return 0;}
/*
*/

提出情報

ジャッジ結果