Submission #7969857

---

Source Code Expand

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

int main()
{
	int N, K;
	cin >> N >> K;
	map<long long, long long> mp;
	for( int i = 0; i < N; i++ ) {
		int A;
		cin >> A;
		int a = __gcd( A, K );
		mp[a]++;
	}

	long long ans = 0;
	for( auto it1 = mp.begin(); it1 != mp.end(); it1++ ) {
		if( it1->first * it1->first % K ) continue;
		ans += it1->second * (it1->second - 1) / 2;
	}
	for( auto it1 = mp.begin(); it1 != mp.end(); it1++ ) {
		for( auto it2 = next( it1, 1 ); it2 != mp.end(); it2++ ) {
			if( it1->first * it2->first % K ) continue;
			ans += it1->second * it2->second;
		}
	}

	cout << ans << endl;
}

Submission Info

Judge Result