コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1745 (記事作成時点)
供養
解法
- 整数 $g \gt 1$ について、整数 $a, b \ge 1$ を用いて $(x, y) = (ag, bg)$ と表せれば最大公約数が $g$ の倍数のペアとなる
- そのような $a, b$ の候補の数 $k_{g}$ は $k_{g} = \lfloor \frac{R}{g} \rfloor - \lceil \frac{L}{g} \rceil + 1$ 種類
- 各素因数を高々1回掛け合わせて作成される $R$ 以下の合成数 $m = \prod_{i} p_{i}^{s_{i} \in \lbrace 0, 1 \rbrace}$ について $S_{m} = (-1)^{(1 + \sum_{i}s_{i})}$ とすると、$g \gt 1$ であるような $(x, y)$ の総数 $X$ が $X = \sum_{m} S_{m}k_{m}(k_{m} - 1)$ で求められる
- $m $ の集合 $M $ および $S_{m}$ を以下のように列挙する
- $R$ 以下の素数を列挙し、$P$ とする
- $M = \emptyset$ とする
- 各 $p_{i} \in P$ について以下のように $M $ を更新する
- $u = \lfloor \frac{R}{p_{i}} \rfloor + 1$ とする
- $M \cap \lbrack 0, u)$ で最大の要素を次の $u$ とし、$M = M \cup \lbrace up_{i} \rbrace, S_{up_{i}} = -S_{u}$ とする
- $M = M \cup \lbrace p_{i} \rbrace, S_{p_{i}} = 1$ とする
- $X$ は $\frac{x}{g} = 1$ もしくは $\frac{y}{g} = 1$ であるような $(x, y)$ も含んでいるので、$L \le g \le R$ について $2(k_{g} - 1)$ を引くことでそれらを排除する
実装
計算量は $O(R \log R)$
公式解説
躓いた点
- $g \gt 1$ である $(x, y)$ の列挙方法の整理と高速化に手こずった
