トップ > AtCoder > ABC230E - Fraction Floor Sum

ABC230E - Fraction Floor Sum

AtCoder AtCoder-Beginner Contest Python 和


【関連】

考え方

$[x]$は他の問題では$\lfloor x \rfloor$で表すことが多いので，こちらを使う．

もちろんそのまま計算しては間に合わないので，$\biggl\lfloor \dfrac{N}{i} \biggr\rfloor = M$となる$M$でループを回せないか考えてみる．つまり，

  • $M$でループさせ
  • ($M$の値)$\times$($M$の値を取る個数)を足していく
という方針が考えられる（*1）．

ここで，

\begin{aligned}
& \biggl\lfloor \frac{N}{i} \biggr\rfloor = M \\
& \Leftrightarrow M \leq \frac{N}{i} < M + 1 \\
& \Leftrightarrow \frac{N}{M + 1} < i \leq \frac{N}{M}
\end{aligned}
だから，$\biggl\lfloor \dfrac{N}{i} \biggr\rfloor = M$となる$i$の個数を$\mathrm{cnt\,}(M)$とすれば
\begin{aligned}
\mathrm{cnt\,}(M)
=\biggl\lfloor \frac{N}{M} \biggr\rfloor
- \biggl\lfloor \frac{N}{M + 1} \biggr\rfloor
\end{aligned}
となる．

しかし，$M$が取り得る値は$1\sim N$まであるので，$M$を全部調べていくのでは，考え方を変える前と計算量が変わらない．


さて，考えて見れば，個数$\mathrm{cnt\,}(M)$は$M$に対して一様に分布するわけではない．$f(i) = N / i$のグラフを考えてみれば，$i$が小さい方が$i$の変化に対して$f(i)$は大きく変化し，$i$が大きくなるにつれて$f(i)$の変化は小さくなる．つまり，$i$が小さい方が$\lfloor N/i \rfloor = M$を満たす$i$の個数は少なくなり，$i$が大きくなるにつれて$\lfloor N/i \rfloor = M$を満たす$i$の個数は多くなる．

$M$でループさせるメリットが有るのは，$\lfloor N/i \rfloor = M$を満たす$i$の個数が大きくなるところである．この領域では，$i$を変えても$M$の変化が小さいため，$i$でループするより$M$でループした方が効率が良い．

以上を定量化する．$i$を1増やしたときに，$\mathrm{cnt\,}(M)$の変化量が$1$より小さければ，$i$より$M$でループした方が効率が良い．つまり，

\begin{aligned}
& \biggl | \frac{\mathrm{d} f}{\mathrm{d} i} \biggr|
= \frac{N}{i^{2}} < 1\\
& \Leftrightarrow \sqrt{N} < i
\end{aligned}
なら$M$でループさせたほうが良い．

この範囲の$M$の個数は

\begin{aligned}
\frac{N}{i} < \sqrt{N}
\end{aligned}
よりたかだか$\sqrt{N}$個なので，$O(\sqrt{N})$で計算できる．

残りの$i\leq \sqrt{N}$の範囲については，愚直に和をとれば$O(\sqrt{N})$で計算できる．

以上より，$O(\sqrt{N})$で問題が解けた．

回答例

N = int(input())

ans = 0
i = 1
while i ** 2 <= N:
  M = N // i
  ans += M
  i += 1

M -= 1
while M >= 1:
  ans += M * ((N // M) - (N // (M + 1)))
  M -= 1

print(ans)

参考

*1:なんとなく，競プロ的にこの方法ぽいな，という感覚がある．