この解説では \(0\) 個の整数のLCMを \(1\) と定め、空列も有効な選び方に含めるとします。

\(A\) の要素のうち \(M\) の約数でないものを選ぶことはないため、そのような値は最初に取り除いておきます。

問題が「LCMが \(M\) の約数となるような選び方」の個数であれば解くのは容易です。具体的には、\(A\) に含まれる \(M\) の約数の個数を \(n\) として \(2^n\) が答えです。

もとの問題を約数包除原理で解くことを考えます。
例えば
「LCMがちょうど72になる選び方の個数」
＝「LCMが72の約数になる選び方の個数」
－「LCMが36の約数になる選び方の個数(2の指数が足りない)」
－「LCMが24の約数になる選び方の個数(3の指数が足りない)」
＋「LCMが12の約数になる選び方の個数(2,3の指数が足りない)」
となります。数式で表せば、\(M\) の素因子を \(p_1,\ldots,p_k\) として

\(\displaystyle \sum_{S\subset \{1,\ldots,k\}} (-1)^{|S|}\left(\text{LCMが}\frac{M}{\prod_{i\in S}p_i}\text{の約数になる選び方の個数}\right)\)
\(=\displaystyle \sum_{S\subset \{1,\ldots,k\}} (-1)^{|S|}2^{\left(A\text{に含まれる}\frac{M}{\prod_{i\in S}p_i}\text{の約数の個数}\right)}\)

です。「\(A\) に含まれる \(X\) の約数の個数」を \(f(X)\) とおきます。\(f(X)\) は \(X\) を固定するごとに \(O(N)\) で求めることができますが、上の式を愚直に計算する \(O(2^kN)\) の解法で実行時間に間に合わせることは困難です。高速化を考えましょう。

次の \(2\) 点に注目します。

• もし \(a\) が \(\frac{M}{\prod_{i\in S}p_i}\) の約数ならば、任意の \(T\subset S\) について、\(a\) は \(\frac{M}{\prod_{i\in T}p_i}\) の約数である
• 「\(a\) が \(\frac{M}{\prod_{i\in S}p_i}\) の約数である」を満たすような極大な\(S\) が一意に定まる（自明ではないが証明略）

よって、(\(X\) ごとに \(f(X)\) を求めるのではなく、) \(A\) の各要素 \(a\) に対して \(2\) 番目の条件にあうような \(S\) をとって、imos法の要領であとから”部分集合に配る”ことで \(f(\frac{M}{なんとか})\) たちを高速に計算することができそうです。この変換はゼータ変換と呼ばれます。その具体的な実装方法はここでは省略します。

(\(M\) が適切な形に素因数分解されている下で) 各 \(a\in A\) に対し 「『\(a\) が \(\frac{M}{\prod_{i\in S}p_i}\) の約数である』を満たすような極大な\(S\) 」を求めるのにかかる \(O(k)\) 時間と、それらを計算し終えたあとのゼータ変換にかかる \(O(k2^k)\) 時間で、必要な全ての \(f(\frac{M}{なんとか})\) たちを求めることができたので、包除原理の式に従って計算することで問題が解けました。