Submission #3570515

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

/*

*/

ll gcd(ll a,ll b){
	if(b==0)return a;
	return gcd(b,a%b);
}

int main(void){
	ll n,k,a[200010],ans=0;
	map<ll,ll> m;
	vector<mp> d;
	cin>>n>>k;
	rep(i,n){
		cin>>a[i];
		m[gcd(k,a[i])]++;//約数に対応させる
	}
	//操作しやすいようにベクトルに変換
	for(auto itr = m.begin(); itr != m.end(); ++itr) {
		d.push_back({itr->first,itr->second});
	}
	//異なるグループから選ぶ
	rep(i,d.size()){
		rep(j,i){
			if((d[i].first*d[j].first)%k==0){
				ans+=d[i].second*d[j].second;
			}
		}
	}
	//同じグループから選ぶ
	rep(i,d.size()){
		if((d[i].first*d[i].first)%k==0){
			ans+=d[i].second*(d[i].second-1)/2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result