DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 : C - ロト2

CとDの間の難易度の問題があってもよかったと思うけどなぁ。
http://ddcc2016-qual.contest.atcoder.jp/tasks/ddcc_2016_qual_c

問題

N要素の数列A[i]と、整数Kが与えられる。
数列中の2要素の対のうち、積がKの倍数になるのは何通りか。

解法

A[i]*A[j]がKの倍数になるなら、GCD(A[i],K)*GCD(A[i],K)もKの倍数になる。
よってA[i]をそれぞれGCD(A[i],K)で置き換えよう。
10^9以下の整数の約数は、最大でも1344通りしかないので、GCD(A[i],K)の値も1344通りしかない。
あとはO(N^2)かかるアルゴリズムで組み合わせを数え上げれば間に合う。

参考：高度合成数のリストhttp://wwwhomes.uni-bielefeld.de/achim/highly.txt

int N,K;

unordered_map<ll,ll> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	ll ret=0;
	FOR(i,N) {
		cin>>x;
		M[__gcd(x,K)]++;
	}
	FORR(r,M) FORR(r2,M) if(r.first*r2.first%K==0) {
		if(r.first==r2.first) ret+=r.second*(r.second-1)/2;
		if(r.first<r2.first) ret+=r.second*r2.second;
	}
	
	cout<<ret<<endl;
}

まとめ

本番はもっと手間取ることをしてしまった。