けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 206 E - Divide Both (青色, 500 点)

AtCoder AtCoder500点 ABC-E 青色diff 補集合を考える添字GCD畳み込みエラトステネスの篩約数系包除包除原理最大公約数条件の言い換え最大公約数の値を固定して考えるある量を固定して考えるテク:スタートを0としてよい制約:数値が10^6以下調和級数数学(整数問題) 約数メビウス関数解空間:O(N^2)通りの選択肢【問題集】整数変数の式で表された条件を扱う探索入力が定数個数え上げ問題中堅以上の典型要素を詰め合わせた教育的問題

約数系包除原理の教育的問題

問題へのリンク

問題概要

整数 $L, R$ が与えられるので、以下の条件を満たす整数 $(x, y)$ の組の個数を求めてください。

$L \le x, y \le R$
$g = {\rm GCD}(x, y)$ としたとき、 $g \neq 1$ , $\frac{x}{g} \neq 1$ , $\frac{y}{g} \neq 1$

制約

$1 \le L \le R \le 10^{6}$

解法 (1)：約数系包除

まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を書いてみました。この問題の解説も次の記事の最後で行ってみました。

流れのみを確認すると、この問題は結局は、各 $k$ に対して

${\rm GCD}(x, y) = k$ , $L \le x, y \le R$ となる $(x, y)$ の個数を求めよ

という問題に帰着される。なお、そうなる過程では、 $\frac{x}{g} = 1$ となるもの (簡単に数えられる) を最後に引くという方針をとることで、 $\frac{x}{g} \neq 1$ という条件を無効化する、みたいなことをやっている。

さて、このように「最大公約数がちょうど $k$ になるような場合を考える」という問題では、約数系包除が活躍することが多い。なぜなら、ちょうど $k$ になる場合を求めるのは難しくても

${\rm GCD}(x, y)$ が $k$ の倍数になる場合の数 ( $L \le x \lt y \le R$ ) を求めることは簡単

だからだ。

${\rm GCD}(x, y)$ が $k$ の倍数
⇔ $x, y$ が $k$ の倍数

が成立するので、条件がとても簡単になる。こういうときは、約数系包除原理が活躍する。計算量は $O(R \log \log R)$ になる。

解法 (2)：調和級数的計算量

約数系包除原理の問題は、調和級数的計算量でも解けることが多い気がする。詳しくは、kyopro_friends さんの公式解説より。

ただし、約数系包除で解ける問題を、調和級数的計算量の理屈で解くと、計算量は $O(R \log R)$ になる。少し遅くなる。

メビウス関数を用いて約数系包除原理をするのは、調和級数的計算量の理屈で解くのを高速化したとみなすこともできる。

解法 (3)：添字 GCD 畳み込み

添字 GCD 畳み込みで殴ることもできる。約数系包除原理の考察が面倒になったら、分かりやすく添字 GCD 畳み込みで殴ってしまうのはとてもいいかもしれない。詳しくは kuprin さんのユーザー解説より。

kanpurin.hatenablog.com

解法 (4)： $O(R^{0.75})$ 解法

maspy さんの記事より。