概要
解答例 （Python）：https://atcoder.jp/contests/abc206/submissions/23640850
解答例（C++）：https://atcoder.jp/contests/abc206/submissions/23641033
公式解説より良い計算量 $O(R^{0.75})$ 時間計算量での解法を紹介します。
半開区間
本解説（および、リンク先の解答例）では、区間に $(L, R] = \{n\in \Z\mid L < n\leq R\}$ という半開区間の記法を用いていきます。正の整数 $d$ に対して
$$ dn \in (L, R] \iff n \in \left(\lfloor L/d\rfloor, \lfloor R/d\rfloor\right]$$
とシンプルに書ける利点があります。
商の列挙
正の整数 $N$ に対して、いろいろな $d$ に対して商 $\lfloor N/d\rfloor$ を考えるとします。これは、約 $2\sqrt{N}$ 通りです。
- $\lfloor N/d\rfloor \leq \sqrt{N}$ となる場合：$\lfloor\sqrt{N}\rfloor$ 通り
- $\lfloor N/d\rfloor > \sqrt{N}$ となる場合：約 $\lfloor\sqrt{N}\rfloor$ 通り（$d$ を数える）
となるためです。なお詳しく計算すると、$2\lfloor\sqrt{N}\rfloor$ 通りまたは $2\lfloor\sqrt{N}\rfloor – 1$ 通りのどちらかであることが分かります。
そこで、次のような問題が考えられます。
- 集合 $\{q = \lfloor N/d\rfloor\mid 1\leq d \leq N\}$ の元 $q$ を列挙せよ
- そのような $q$ に対して、$\lfloor N/d\rfloor = q$ となる $d$ の範囲 $(L, R]$ を求めよ
先に、後者の問題を解きましょう。$$\lfloor N/d\rfloor = q\iff q\leq \frac{N}{d}< q+1\iff \frac{N}{q+1} < d\leq \frac{N}{q}$$ ですから、$L = \lfloor N/(q+1)\rfloor$, $R = \lfloor N/q\rfloor$ とすればよいことが分かります。
すると、$q$ の列挙も簡単です。$q$ を昇順（したがって $d$ は降順）に列挙することにします。いまの $q$ に対する $d$ の範囲が $(L, R]$ であるとすると、「次の $q$」は $d = L$ から得られる、つまり $q = \lfloor N / L\rfloor$ であることが分かります。
例えば次の要領です。
def generate_quotient(N):
"""
商 q および、N//d == q となる d の範囲 (L, R] を生成する
"""
R = N
while R:
q = N // R
L = N // (q + 1)
yield (L, R, q)
R = L
同じことですが、$q = 1$ からはじめて商を昇順に列挙することもできます。
商の組の列挙
$A, B$ という $2$ つの数があるときに、組 $\left(\lfloor A/d\rfloor, \lfloor B/d\rfloor\right)$ としてありうるものを数えましょう。「商の組の変化点」はどちらかの「商の変化点」なので、このような組は、$\Theta(\sqrt{A} + \sqrt{B})$ 通りあります。
その列挙も、やはり $d = 1$ から始めて、同じ商の組を与える区間 $(L,R]$ を次々と求めていくことで解決します。
def generate_quotient_pair(A, B):
"""
(L, R] 上で (A//d, B//d) == (qA, qB) となるような
商の組 (qA, qB) および (L, R] を生成する
"""
R = max(A, B)
while R:
qA, qB = A // R, B // R
L = max(A // (qA + 1), B // (qB + 1))
yield L, R, qA, qB
R = L
解法
問題文の $L$ から $1$ 引いたものを改めて $L$ と書くことにします。扱う範囲は $(L, R]$ です。
$3$ つの条件があるため、それらで包除原理を考えます。$x, y \in (L, R]$ の範囲で
- 全体
- $g = 1$ となるものの個数
- $g = x$ となるものの個数
- $g = y$ となるものの個数
- $g = x = 1$ となるものの個数
- $\vdots$
等を数え上げて、足し引きすれば答が得られます。それぞれ、以下の時間計算量で計算が可能です。
- $g = 1$ となるものの個数：$O(R^{0.75})$ 時間
- $g = x$ となるものの個数：$O(R^{0.5})$ 時間
- それ以外：$O(1)$ 時間
「それ以外」に相当するものは簡単なので省略します。$1\in (L, R]$ であるかどうか（$L = 0$ であるかどうか）にしたがって少し扱いが変わるところに気を付けましょう。
$g = x$ となるものの個数の計算
$x\mid y$ となるものの個数といってもよいです。$x = d$ ごとに数えます。
固定された $d$ に対して、計算対象は $\lfloor R/d\rfloor – \lfloor L/d\rfloor$ です。したがって、組 $(\lfloor L/d\rfloor, \lfloor R/d\rfloor)$ が定数となる区間 $O(R^{0.5})$ 個に分けることで、$O(R^{0.5})$ 時間で計算することができます。
$g = 1$ となるものの個数の計算
$(L,R]$ に対してこれを計算した値を $f(L, R)$ と書くことにします。$f(L, R)$ は、次のように計算できます。
- まずは、$L < x, y\leq R$ となる全ての組 $(x,y)$ を数える。これは $(R-L)^2$ 通りである。
- 各 $2\leq d \leq R$ に対して、組 $(x,y)$ のうちで $\gcd(x,y) = d$ となるものを引く
後者はどのように計算できるでしょうか。$\gcd(x,y) = d$ であるような組 $(x,y)$ は、$\gcd(x,y) = 1$ であるような組 $(x’, y’)$ を用いて $(dx’, dy’)$ と表すことができます。さらに、$dx’, dy’ \in (L, R]\iff x’, y’ \in (\lfloor L/d\rfloor, \lfloor R/d\rfloor]$ ですから、この数え上げは $f(\lfloor L/d\rfloor, \lfloor R/d\rfloor)$ と表すことができます。したがって、次の漸化式が得られました：
$$f(L, R) = (R-L)^2 – \sum_{2\leq d\leq R}f(\lfloor L/d\rfloor, \lfloor R/d\rfloor)$$
仮に、小さな $(l,r)$ に対して $f(l,r)$ が計算済であるとします。この和 $\sum_d$ は、愚直に計算すると $O(R)$ 時間が必要ですが、商の組が定数である区間をひとまとめに計算することで、$f(L, R)$ は $O(R^{0.5})$ 時間で計算できることが分かります。
あとはこれをもとに、メモ化再帰で計算すれば、後述のように計算量 $O(R^{0.75})$ 時間が実現されます。
計算量解析
まず、上の再帰によって計算対象となる $f(l, r)$ は、すべて、$(l,r) = (\lfloor L/d\rfloor, \lfloor R/d\rfloor)$ と書けるものです（そのような $(l,r)$ に対する $(\lfloor l/d\rfloor, \lfloor r/d\rfloor)$ も再びこの形で書ける組であるため）。したがって、そのような組全体を $A$ としたとき、全体の計算量は
$O\left(\sum_{(l,r)\in A} \sqrt{r}\right)$
となることが分かります。この $\sum$ を評価しましょう。
- $1\leq d\leq \sqrt{R}$ から作られる組 $(l,r)$ に対する総和は高々 $\sum_{d=1}^{\sqrt{R}}(R/d)^{0.5} = O(R^{0.75})$ である。
- $\sqrt{R} \leq d$ から作られる組 $(l,r)$ について、組数は $|A|$ 以下であり、$r = R/d\leq R^{0.5}$ であるため、 $\sqrt{r}$ の総和は $O(R^{0.75})$ である。
となって、全体の計算量が $O(R^{0.75})$ であることが確かめられました。
