yukicoder No.1276 3枚のカード - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

${1\leq A,B,C\leq N}$ かつ ${A}$ は ${B}$ の約数でも倍数でもなく, ${B}$ は ${C}$ の約数であるような相異なる3数は何通りあるか.

${1\leq N\leq 10^9}$

解説

求めるものは「 ${A\nmid B}$ かつ ${B\nmid A}$ かつ ${B\mid C}$ かつ ${A,B,C}$ は相異なる」ようなものの数.
これを言い換えて次のものを求める「 ${A,B,C}$ は相異なるとして, ( ${B\mid C}$ の数)-( ${B\mid A}$ かつ ${B\mid C}$ の数)-( ${A\mid B}$ かつ ${B\mid C}$ の数)」

ベン図で表すと以下の部分を求めることとなる.
${A\neq B}$ を考えているので ${A\mid B}$ と ${B\mid A}$ の共通部分はない.

${B\mid C}$ となる ${(A,B,C)}$ の数

　 ${B}$ を固定すると ${C=kB (k\geq 2)}$ と表すことができる.
　よって ${2\leq k\leq \lfloor \frac{N}{B}\rfloor}$ を満たす ${k}$ の数 ${\lfloor \frac{N}{B}\rfloor -1}$ が ${C}$ の数となる.これに残りの ${N-2}$ 個から ${A}$ を選ぶ.
　①　 $(N-2)\sum_{B=1}^{N}(\lfloor\frac{N}{B}\rfloor -1)$

${B\mid A}$ かつ ${B\mid C}$ となる ${(A,B,C)}$ の数

　同様にして ${\lfloor \frac{N}{B}\rfloor -1}$ から異なる2つを選ぶ.
　②　 $\sum_{B=1}^{N}(\lfloor\frac{N}{B}\rfloor -1)(\lfloor\frac{N}{B}\rfloor -2)$

${A\mid B}$ かつ ${B\mid C}$ となる ${(A,B,C)}$ の数

　 ${A}$ を固定すると ${B=kA, C=klA (k\geq 2, l\geq 2)}$ と表すことができる.
　 ${kl\leq \lfloor\frac{N}{A}\rfloor, k\geq 2, l\geq 2}$ を満たす ${(k,l)}$ の数を求める.
　③　 $\sum_{A=1}^{N}\sum_{k=2}^{\lfloor\frac{N}{A}\rfloor}(\lfloor\frac{\lfloor\frac{N}{A}\rfloor}{k}\rfloor -1)$

①－②－③が答えだが, この式のまま愚直に求めても間に合わない.
$\sum_{i=1}^{N}\lfloor \frac{N}{i}\rfloor$ は ${O(\sqrt{N})}$ で求められる.

具体的には, ${i\leq \sqrt{N}}$ ならそのまま ${\lfloor\frac{N}{i}\rfloor}$ の和を愚直に求める.
${i>\sqrt{N}}$ の場合, ${\sqrt{N}>\frac{N}{i}}$ であるので ${\lfloor\frac{N}{i}\rfloor}$ の種類は ${O(\sqrt{N})}$ 個. ${\lfloor\frac{N}{i}\rfloor =k(1\leq k\leq \sqrt{N})}$ となる ${i}$ の個数は

${\begin{array}{}\displaystyle &\lfloor\frac{N}{i}\rfloor\leq \frac{N}{i} < \lfloor\frac{N}{i}\rfloor+1\\ \displaystyle \Longleftrightarrow &k\leq \frac{N}{i} < k+1\\ \displaystyle \Longleftrightarrow &\frac{N}{k+1} < i\leq \frac{N}{k}\\ \displaystyle \Longleftrightarrow &\lfloor\frac{N}{k+1}\rfloor+1\leq i\leq \lfloor\frac{N}{k}\rfloor\end{array}}$

以上より ${\lfloor\frac{N}{k}\rfloor-\lfloor\frac{N}{k+1}\rfloor}$ 個となる.これに ${k}$ をかけたものの総和が求めるものになる. したがって, ${O(\sqrt{N})}$ で求めることができた.

①と②は同様にして求めることができる. ③も同様にした場合, ${O(\sqrt{N})}$ の計算を ${O(\sqrt{N})}$ 回行っているように見えるが, 実は ${O(N^{\frac{3}{4}})}$ で求められる.

${A\leq \sqrt{N}}$ のときの計算回数は ${O(\sum_{A=1}^{\sqrt{N}}\sqrt{\frac{N}{A}})=O(N^{\frac{3}{4}})}$
${A>\sqrt{N}}$ のときは ${O(\sum_{k=1}^{\sqrt{N}}\sqrt{k})=O(N^{\frac{3}{4}})}$
どちらも(調和級数みたいに)区分求積法などで評価してやれば ${O(N^{\frac{3}{4}})}$ となる.

提出プログラム

https://yukicoder.me/submissions/575639

感想

めっちゃ勉強になった. ${A|B|C}$ 求めるやつで ${B}$ 固定してわけわからなくなった.