Submission #7968693

---

Source Code Expand

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

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

	long long ans = 0;
	for( int i = 0, j = N - 1; i < mp[K]; i++, j-- ) {
		ans += j;
	}
	vector<int> d;
	for( int i = 2; i * i <= K; i++ ) {
		if( K % i == 0 ) {
			d.push_back( i );
			if( K / i != i ) d.push_back( K / i );
		}
	}
	for( int i = 0; i < d.size(); i++ ) {
		for( int j = i + 1; j < d.size(); j++ ) {
			if( d[i] * d[j] % K ) continue;
			ans += mp[ d[i] ] * mp[ d[j] ];
		}
	}

	cout << ans << endl;
}

Submission Info

Judge Result