Submission #7795208

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define rep(i,m,n) for(int i=m;i<n;i++)

typedef long long ll;

ll gcd(ll a, ll b){
 while(a%b){
  ll r=a%b;
   a=b;
   b=r;
 }
return b;
}

int main(){
   cin.tie(nullptr);
  ios::sync_with_stdio(false);

 ll n,k;
  cin >> n >> k;
 map<ll,ll> mp;
  rep(i,0,n){
   ll a;
    cin >> a;
   ll g=gcd(a,k);
    mp[g]++;
  } 
  
  ll res=0,num=0;
  for(auto p:mp){
    for(auto q:mp){
    if((p.first*q.first)%k==0) {
       if(p.first!=q.first) num+=p.second*q.second;
       else res+=p.second*(q.second-1)/2;
    }
    }
  }
  num/=2;
  res+=num;
  
  cout << res << endl;

}

Submission Info

Judge Result