解法1(DP解)

以下の DD を考えます.

DgD_g : 数列AAの長さKKの部分列で,最大公約数がggとなるようなものの数

また,

BgB_g : 数列AAに含まれる数で gg の倍数であるものの個数

とすると,DDについて以下の漸化式(DP)が成り立ちます.

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

従って,BiB_iDiD_i を,iiMM の倍数であるものについて全て求めることで DMD_M を求めることができます.

BM,B2M,B3M,B4M, B_M, B_{2M}, B_{3M}, B_{4M}, \ \dots を求める計算量は

O(1iAMAiM)=O(AM1iAM1i)=O(AMlogAM)\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})

であり十分高速です(調和級数). DD についても,大きい方から順に求めていくことで,DM,D2M,D3M,D4M, D_M, D_{2M}, D_{3M}, D_{4M}, \ \dots を同じく

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

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

解法2(包除原理を使った解法)

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

MM の倍数ではない要素は削除してもよいため,以下では MM の倍数を除いた数列AA を考えます.
数列AA の要素を全て MM で割ってできる数列を PP とします.ここで,以下で定義される XsX_s を考えます.

XsX_s : 数列PP の要素のうち,その素因数の(重複を除いた)集合に,素数の部分集合ss を含むものの個数

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

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

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

解法1のコード例(Python)

解法2のコード例(C++)