問題概要
リンク先 を見てください
解法
制約的に、bit DP をしたい。
$$ \begin{aligned} \mathrm{dp}(S) :=\; & 1 \text{ 以上 } M \text{ 以下の整数 } x \text{ であって、}\\ &\text{ある } i\in S \text{ が存在して } A_i \text{ が } x \text{ を割り切るようなものの個数} \end{aligned} $$
がすべての $S\subseteq\{1,\ldots,N\}$ に対して求まればこの問題が解ける。
集合 $S$ に対して、任意の $i\in \{1,\ldots,N\} - S$ を一つ選んで添加することを考える。即ち、$\mathrm{dp}(S)$ が既知として、$\mathrm{dp}(S\cup\{i\})$ の値を求める。
$\mathrm{dp}(S\cup\{i\})$ と $\mathrm{dp}(S)$ の差分は、以下を全て満たすような整数 $x$ の個数である。
$$ \begin{aligned} & 1\leq x\leq M, \\ & A_i \mid x, \\ & A_j \nmid x\quad \forall j\in S. \end{aligned} $$
これは、2 つめの条件を考慮して $x=x'A_i$ とおけば、
$$ \begin{aligned} & 1\leq x'\leq \left\lfloor M/A_i \right\rfloor, \\ & A_j/\gcd(A_i, A_j) \nmid x'\quad \forall j\in S, \end{aligned} $$
を満たす整数 $x'$ の個数と言い換えられる。従って、包除原理により一つの $\mathrm{dp}(S\cup\{i\})$ を $\Theta(N\cdot 2 ^ {|S|})$ で求められる。具体的には、
$$ \begin{aligned} \mathrm{dp}(S\cup\{i\}) &= \mathrm{dp}(S)+\sum _ {T\subseteq S} (-1)^{|T|} \left\lfloor \dfrac{\left\lfloor \dfrac{M}{A_i}\right\rfloor}{\underset{j \in T}{\mathrm{lcm}} \dfrac{A_j}{\gcd(A_i, A_j)}} \right\rfloor \\ &=\mathrm{dp}(S)+\sum _ {T\subseteq S} (-1)^{|T|} \left\lfloor \dfrac{M}{\underset{j \in T\cup\{i\}}{\mathrm{lcm}}A_j} \right\rfloor \end{aligned} $$
とすればよい。
しかし、このままでは間に合わないので高速化する必要がある。計算をもう少し進めると、
$$ \begin{aligned} \mathrm{dp}(S) &=\mathrm{dp}(\emptyset)+\sum _ {\emptyset\neq T\subseteq S} (-1)^{|T|+1} \left\lfloor \dfrac{M}{\underset{j \in T}{\mathrm{lcm}}\ A_j} \right\rfloor\\ &=M-\sum _ {T\subseteq S} (-1)^{|T|}\left\lfloor \dfrac{M}{\underset{j \in T}{\mathrm{lcm}}\ A_j} \right\rfloor \end{aligned} $$
を得る。高速ゼータ変換を用いることで、すべての $S\subseteq \{1,\ldots,N\}$ に対する $\mathrm{dp}(S)$ を $\Theta(N\cdot 2 ^ N\cdot \log M)$ で求めることができる。なお、$\mathrm{lcm}$ の計算も同時に bit DP で求めることで $\Theta((N + \log M) \cdot 2 ^ N)$ へと計算量を落とすことができる。
