Submission #967754

---

Source Code Expand

#include <map>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

// ------------ Greatest Common Divisor (Update 8/7) ------------ //
inline unsigned long long gcd(unsigned long long x, unsigned long long y) {
	while (y != 0) {
		unsigned long long r = x;
		x = y;
		y = r % y;
	}
	return x;
}

// ------------ Prime Factorization (Update 8/6) ------------ //
std::map<unsigned long long, unsigned> prime_factorize(unsigned long long x) {
	std::map<unsigned long long, unsigned> ret;
	for (unsigned i = 2; 1ULL * i * i <= x; i++) {
		while (x % i == 0) x /= i, ret[i]++;
	}
	if (x != 1) ret[x]++;
	return ret;
}

// ------------ Enumerate Divisors (Update 10/27) ------------ //
std::vector<unsigned long long> calc_divisors(unsigned long long x) {
	std::map<unsigned long long, unsigned> res = prime_factorize(x);
	std::vector<unsigned long long> ret; ret.push_back(1);
	for (std::pair<unsigned long long, unsigned> w : res) {
		int s = ret.size();
		unsigned long long mul = 1;
		for (int i = 0; i < w.second; i++) {
			mul *= w.first;
			for (int j = 0; j < s; j++) ret.push_back(ret[j] * mul);
		}
	}
	sort(ret.begin(), ret.end());
	return ret;
}

int n, m, a[200009];
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<unsigned long long> v = calc_divisors(m);
	vector<int> c(v.size());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < c.size(); j++) {
			if (a[i] % v[j] == 0) c[j]++;
		}
	}
	long long ret = 0;
	for (int i = 0; i < n; i++) {
		int e = m / gcd(a[i], m);
		int ptr = lower_bound(v.begin(), v.end(), e) - v.begin();
		ret += c[ptr];
	}
	for (int i = 0; i < n; i++) {
		if (1LL * a[i] * a[i] % m == 0) ret--;
	}
	cout << ret / 2 << endl;
	return 0;
}

Submission Info

Judge Result