DDCC2016 予選 C ロト2 - 足跡-sokuseki-

$N$ 個の整数があり、 $i$ 番目の整数は $A_i$ である。

$A_i \times A_j$ が $K$ の倍数となるような $i$ と $j$ の組み合わせ $( i , j )$ が何通りあるか求めよ。

制約
$2 \le N \le 200000$
$1 \le A_i \le 10^9$
$1 \le K \le 10^9$

積が $K$ の倍数になればいいのだから、それぞれの $A_i$ において必要な情報は、 $K$ の約数のうちどれが含まれているか。
よって、それぞれの $A_i$ について、 $gcd(A_i , K)$ を求める。
あとはそれらを2つかけて $K$ の倍数にできるかを判定して数え上げればいい。

ってことまで自力で思いついて、具体的な方法が思い浮かばなかった。ので解説を見た。

$1 \le K \le 10^9$ だから、 $K$ の約数の個数は高々1500個くらいらしい。よって、連想配列か何かに $gcd(A_i , K)$ を記録していって、2重ループで全探索すれば良い。

連想配列は滅多に使わないので、範囲forというものを初めて知った。
範囲for文 - cpprefjp C++日本語リファレンス