コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 2068 (記事作成時点)
供養
解法
- 任意の $A \le n \lt m \le B$ について、 $\mathit{GCD}(n, m) = \mathit{GCD}(n, m - n) \le m - n \le B - A$ である
- 従って、ある整数集合 $S \subseteq \lbrack A, B \rbrack$ の要素が互いに素であるとき、$2 \le p \le B - A$ である素数 $p$ を約数にもつ要素は高々ひとつ
- $2 \le p \le B - A$ の範囲の素数集合を $P$ として、$p_{j} \in P$ を約数にもつ要素が1つだけの集合の数についてのbit DPをすることができる
- $C_{i} = \sum_{p_{j} \in P | (A + i) \equiv 0\; \mathrm{MOD}\; p_{j}} 2^{j}$ とすると、$S$ を表現する数 $F(S)$ は以下のように表現できる
\begin{align}
F(S) =
\begin{cases}
0 & (S = \emptyset) \\
F(S \setminus \lbrace C_{i} \rbrace)\; \mathrm{bitOR}\; C_{i} & (\text{else})
\end{cases}
\end{align}
- $\mathit{DP}_{i, j}$ を $S$ を構成する各要素が高々 $A + i$ のときに、$F(S) = j$ かつ互いに素である集合の数とすればよい
- $\mathit{DP}_{i - 1, j}\; \mathrm{bitAND}\; C_{i} \gt 0$ ならば互いに素でなくなる
実装
計算量は $O(N2^{|P|})$、ここで $B - A \le 72$ なので $|P| \le 20$ である
公式解説
躓いた点
