解法1（DP解）

以下の $D$ を考えます．

$D_g$ : 数列$A$の長さ$K$の部分列で，最大公約数が$g$となるようなものの数

また，

$B_g$ : 数列$A$に含まれる数で $g$ の倍数であるものの個数

とすると，$D$について以下の漸化式（DP）が成り立ちます．

$D_g = \ _{B_g}\mathrm{C}_K \ - D_{2g} - D_{3g} - D_{4g} - D_{5g} - \ \dots$

従って，$B_i$ と $D_i$ を，$i$ が $M$ の倍数であるものについて全て求めることで $D_M$ を求めることができます．

$B_M, B_{2M}, B_{3M}, B_{4M}, \ \dots$ を求める計算量は

$\displaystyle \mathrm{O}(\sum_{1 \leq i \leq \frac{A}{M}}\frac{A}{i*M}) = \mathrm{O}(\frac{A}{M}\sum_{1 \leq i \leq \frac{A}{M}}\frac{1}{i}) = \mathrm{O}(\frac{A}{M} \log \frac{A}{M})$

であり十分高速です（調和級数）． $D$ についても，大きい方から順に求めていくことで，$D_M, D_{2M}, D_{3M}, D_{4M}, \ \dots$ を同じく

$\displaystyle \mathrm{O}(\frac{A}{M} \log \frac{A}{M})$

で求めることができます．

解法2（包除原理を使った解法）

testerのあぷりしあです。writerの解説と本質的には同じと考えられますが、包除原理の式で考えることにより、より見慣れた形で書くことができます。

$M$ の倍数ではない要素は削除してもよいため，以下では $M$ の倍数を除いた数列$A$ を考えます．
数列$A$ の要素を全て $M$ で割ってできる数列を $P$ とします．ここで，以下で定義される $X_s$ を考えます．

$X_s$ : 数列$P$ の要素のうち，その素因数の（重複を除いた）集合に，素数の部分集合$s$ を含むものの個数

集合$s$ のサイズを $\mathrm{size}(s)$ と表現すると、答えは包除原理により、

$\displaystyle \sum_{s} \ _{X_s} C_k \times (-1)^{\mathrm{size}(s)}$

として求めることができます。
$X_s$ を求める前計算がボトルネックとなり、計算量はwriterの解説と同じ $\displaystyle \mathrm{O}(\frac{A}{M} \log \frac{A}{M})$ になります。

解法1のコード例（Python）

解法2のコード例（C++）