Submission #967488

---

Source Code Expand

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

#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using ll = long long; using ull = unsigned long long; using pii = pair<int, int>;
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
static const int MOD = 1e9 + 7;

//最大公約数
int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }

//約数を求める 未ソート
vector<int> divisor(int x) {
	vector<int> ret;
	int i;
	for (i = 1; i*i < x; i++) {
		if (x%i)continue;
		ret.emplace_back(i);
		ret.emplace_back(x / i);
	}
	if (i*i == x)ret.emplace_back(i);
	return ret;
}

signed main() {
	int N, K; cin >> N >> K;
	vector<int> d = divisor(K);
	dumpc(d);
	map<int, int> mp;
	rep(i, 0, d.size()) {
		mp[d[i]] = 0;
	}

	vector<int> A(N);
	rep(i, 0, N) {
		cin >> A[i];
		mp[gcd(A[i], K)]++;
	}

	ll cnt = 0;
	rep(i, 0, d.size()) {
		rep(j, i, d.size()) {
			if (d[i] * d[j] % K == 0) {
				if (i == j)cnt += mp[d[i]] * (mp[d[i]] - 1) / 2;
				else cnt += mp[d[i]] * mp[d[j]];
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

Submission Info

Judge Result