AtCoder Beginner Contest 206（Sponsored by Panasonic）E,F問題メモ

E - Divide Both

やたらユーザー解説が充実してるね。解説書きたい欲が刺激される問題なんだろうか。

ともに $L$ 以上 $R$ 以下の整数のペア $(x,y)$ で、以下の条件を全て満たすものの個数を求めよ
条件
- $g=GCD(x,y)$ として、
  - $g \neq 1$
  - $\frac{x}{g} \neq 1$
  - $\frac{y}{g} \neq 1$
$1 \le L,R \le 10^6$

いろいろな解法がある。

まず、GCDが1にならないペアの個数を求める。これで1つめの条件をクリアするものが全て揃う。
その後、2,3番目の条件に違反するものを除けば答えとなる。
一度に全条件を考える必要は無く、分けて考えられることに気付くと、幾分かスッキリする。

GCDが「ちょうどある値 $g$ 」になる $(x,y)$ の組は直接的に求めにくいが、「 $g$ の倍数」になる組の個数なら簡単に求められる。

とすると、 $C_g=\left \lfloor \dfrac{R}{g} \right \rfloor - \left \lfloor \dfrac{L-1}{g} \right \rfloor$ となり、 $C_g$ 個から2つ選べばよいので $C_g^2$ 通りの組ができる。

L, R = 5, 15
g = 3

L以上R以下のgの倍数: 6  9 12 15  →  ペアは16通り

この内、GCDが「ちょうど $g$ 」以外である組のGCDは $2g,3g,...$ であるはずなので、「ちょうど $2g$ 」「ちょうど $3g$ 」……の組の個数を先に求めておいて全て除けば「ちょうど $g$ 」の個数が求まる。

g = 15 :  (15, 15)
g = 12 :  (12, 12)
g = 9  :  ( 9,  9)
g = 6  :  ( 6,  6), ( 6, 12), (12,  6)

ちょうど 3 になるのは、16 - 6 = 10 ペア

現在の $g$ を求めるには、 $2g,3g,...$ など自身より大きい場合の数が先に求まっていて欲しいので、 $g$ は大きい方から決定するのがポイント。

$g \ge 2$ の全ペア数の総和が「GCDが1にならないペア数」となる。

計算量は $O(R \log{R})$ となる。

2,3番目の条件は、言い換えると「 $x$ が $y$ の倍数」「 $y$ が $x$ の倍数」という関係である。

片方の数 $L \le k \le R$ を固定し、 $R$ 以下で $k$ の倍数となる相方が何個取れるかを求めていけば、その総和が2,3番目の条件に違反するものとなる。

その個数は、 $2\dfrac{R}{k}-1$ となる。
「 $x$ が $k$ の場合」「 $y$ が $k$ の場合」で各 $\dfrac{R}{k}$ 個ずつあるが、ともに $k$ である $(k,k)$ を重複して数えているので1つ除く、という計算になる。

Grundy数。

Grundy数は、Nim（石取りゲーム）の解法に使えるのが代表的な例ではあるが、「最初から山が複数個ある状態で個々の山のGrundy数を求め、XORを取る」だけのものと考えていると、ちょっと発想しにくいかも知れない。

「山が最初は1つで、1回の操作毎に複数の山に分割される」場合も使える。

|---1----|     |--3--|
       |---2----|
  |-4-|   |-5-|

区間1～5が残っている状態のgrundy数を $g(\{1,2,3,4,5\})$ と表現することにする。

たとえば区間5を選択すると、左 $\{1,4\}$ と右 $\{3\}$ の2つの山に分けられる。
もうこの2つが1回の操作で同時に変化することはない。

この場合、遷移先のgrundy数はこの2つの山のgrundy数のXOR、つまり $g(\{1,4\}) \oplus g(\{3\})$ となる。

計算過程は略すが、 $g(\{1,4\})=1, g(\{3\})=1$ なので、
「 $\{1,2,3,4,5\}$ から区間 $5$ を選んだ場合の遷移先grundy数は $0$ 」となる。

grundy数は、「その状態から遷移できない、最小の非負整数」なので、同じことを区間1～4に対してもやる。

より、 $g(\{1,2,3,4,5\})=2$ となる。

1つの区間を選んだとき、どのように分割されるかを求める部分で実装に少し迷うが、 $N \le 100$ で少ないので、区間を仮定するたびに毎回 $N$ 個を走査して分割後の左/右に含まれるどうかを調べればよい。