Submission #968116

---

Source Code Expand

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#define ALL(v) begin(v),end(v)
#else
#define ALL(v) (v).begin(),(v).end()
#endif

using namespace std;


namespace{
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8

vector<int> div, cntk;
int encode(const vector<int> &cnt){
	int e = 0;
	for(size_t i = 0; i < cnt.size(); ++i){
		e = e * (cntk[i] + 1) + cnt[i];
	}
	return e;
}

LL solve(){
	LL n, k0;
	cin >> n >> k0;

	LL k = k0;
	for(LL i = 2; i * i <= k; ++i){
		int c;
		for(c = 0; k % i == 0; ++c){ k /= i; }
		if(c){
			div.push_back(i);
			cntk.push_back(c);
		}
	}
	if(k > 1){
		div.push_back(k);
		cntk.push_back(1);
	}
	int sz = div.size();
	LL ans = 0;
	int maxe = encode(cntk);
	vector<LL> cs(maxe + 1);
	for(int i = 0; i < n; ++i){
		LL a;
		cin >> a;
		vector<int> v(sz);
		for(int j = 0; j < sz; ++j){
			int c;
			for(c = 0; a % div[j] == 0; ++c){ a /= div[j]; }
			v[j] = min(c, cntk[j]);
		}
		int e = encode(v);
		++cs[e];
	}
	VV(int) encs(maxe + 1);
	vector<int> tmp = cntk;
	while(1){
		int e1 = encode(tmp);
		encs[e1] = tmp;

		int j;
		for(j = 0; j < sz && !tmp[j]; ++j){
			tmp[j] = cntk[j];
		}
		if(j == sz){ break; }
		--tmp[j];
	}

	for(int e1 = 0; e1 <= maxe; ++e1)
	for(int e2 = e1; e2 <= maxe; ++e2){
		bool ok = true;
		for(int i = 0; i < sz; ++i){
			if(encs[e1][i] + encs[e2][i] < cntk[i]){
				ok = false;
				break;
			}
		}
		if(ok){
			if(e1 == e2){
				ans += cs[e1] * (cs[e1] - 1) / 2;
			}
			else{
				ans += cs[e1] * cs[e2];
			}
		}
	}

	return ans;
}

void mainmain(){
	cout << solve() << endl;
}



}
int main() try{
//	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	cerr << fixed << setprecision(4);
	mainmain();
}
catch(...){}

Submission Info

Judge Result