解法1(DP解)
以下の D を考えます.
Dg : 数列Aの長さKの部分列で,最大公約数がgとなるようなものの数
また,
Bg : 数列Aに含まれる数で g の倍数であるものの個数
とすると,Dについて以下の漸化式(DP)が成り立ちます.
Dg= BgCK −D2g−D3g−D4g−D5g− …
従って,Bi と Di を,i が M の倍数であるものについて全て求めることで DM を求めることができます.
BM,B2M,B3M,B4M, … を求める計算量は
O(1≤i≤MA∑i∗MA)=O(MA1≤i≤MA∑i1)=O(MAlogMA)
であり十分高速です(調和級数). D についても,大きい方から順に求めていくことで,DM,D2M,D3M,D4M, … を同じく
O(MAlogMA)
で求めることができます.
解法2(包除原理を使った解法)
testerのあぷりしあです。writerの解説と本質的には同じと考えられますが、包除原理の式で考えることにより、より見慣れた形で書くことができます。
M の倍数ではない要素は削除してもよいため,以下では M の倍数を除いた数列A を考えます.
数列A の要素を全て M で割ってできる数列を P とします.ここで,以下で定義される Xs を考えます.
Xs : 数列P の要素のうち,その素因数の(重複を除いた)集合に,素数の部分集合s を含むものの個数
集合s のサイズを size(s) と表現すると、答えは包除原理により、
s∑ XsCk×(−1)size(s)
として求めることができます。
Xs を求める前計算がボトルネックとなり、計算量はwriterの解説と同じ O(MAlogMA) になります。
解法1のコード例(Python)
解法2のコード例(C++)