0 はじめに
0-1 あいさつ
こんにちは。
0-2 記事の説明
競プロで稀に用いられるテクニック「商列挙」について説明します。
商列挙の説明や証明、実装を書きました。
0-3 動機
ABC296-Dを解いてる時に「あーなんか商列挙みたいなのあったな～」って思って思い出したので書きます。
1 本題
1-1 商列挙とは
商列挙とは、名前だけでは中々分かりづらい内容ですが、次のようなテクニックを指します。
ある自然数$N$について、$\lfloor \frac{N}{i} \rfloor(1 \leq i \leq N)$の値を$O(\sqrt N)$で全て列挙する。
商というのは$\lfloor \frac{N}{i} \rfloor$の部分を指しているのですね。
列挙の計算量と同じく、商の値の種類も$O(\sqrt N)$種類です。
確かに言われてみればそんな気はしますが何故平方根になるのでしょうか。
1-2 平方根になる証明
証明します。
まず、「自然数$N$の商の値の種類」は、次のように言い換えることができる。
(関数$f(x)=\lfloor \frac{N}{x} \rfloor(1 \leq x \leq N)$は広義単調減少である為)
$\lfloor \frac{N}{i} \rfloor \neq \lfloor \frac{N}{i+1} \rfloor$(...①)なる$i(1 \leq i \leq N-1)$の数。
よってこれを求めればよいことになる。
$(1) \frac{N}{i}-\frac{N}{i+1} \geq 1 $の場合
整数部分の差は必ず1以上であるから、①は絶対に成り立つ。
これを満たす$i$の範囲は、
\begin{align*}
\frac{N}{i}-\frac{N}{i+1} \geq 1 &\Leftrightarrow \frac{N}{i(i+1)} \geq 1\\
&\Leftrightarrow N \geq i(i+1)
\end{align*}
即ち、凡そ$i \leq \sqrt N$である。…②
従って、この範囲にある商は約$\sqrt N$種類である。
$(2) \frac{N}{i}-\frac{N}{i+1} ＜ 1 $の場合
②により、$\frac{N}{i}-\frac{N}{i+1} ＜ 1$を満たす$i$の範囲は$\sqrt{N} \leq i \leq N$であるから、$\lfloor \frac{N}{i} \rfloor$の値は$1$以上$\sqrt{N}$以下を取る。
従って、この範囲にある商も約$\sqrt N$種類である。
以上より、$\lfloor \frac{N}{i} \rfloor(1 \leq i \leq N)$の種類数は$O(\sqrt N)$個である。
1-3 実装
1-3-1 一つ目の実装
上の事実を使います。
確実に連続して商が存在する区間は凡そ$[1,\sqrt N]$ですから、残りの部分を調べればよいです。
$i(1 \leq i \leq \sqrt{N}+10)$(10は保険かけてます)くらいについて、$\lfloor \frac{N}{i} \rfloor$を列挙し、その中の最小以下の自然数を全て加えておけばよいです。
コードを見た方が早いと思います。
N=int(input())
L=[]
for i in range(1,int(N**0.5)+10): #証明の(1)の部分
L.append(N//i)
for i in range(L[-1]-1,0,-1): #(2)
L.append(i)
#Lは降順になっている
+10で保険を掛けているので重複する可能性が高いですが、それはsetとかで管理しておけば大丈夫だと思います。(計算量重くなりそうですが)
又、商が$i$の区間も同時に列挙したい場合はappendの部分をいい感じに改造すればいいです。
1-3-2 while文を用いた実装
N=int(input())
L=[]
l=1
while l<=N:
L.append(N//l)
l=N//(N//l)+1
$l$は、商が$\lfloor \frac{N}{i} \rfloor$となる$i$のうち最小のものをとるようになっています。
なのでこんな単純なコードでも商列挙ができます。
これで動く証明はここでは行いませんが考えてみると勉強になるでしょう。
計算量は、勿論商の種類数に等しく$O(\sqrt N)$です。
1-4 商列挙を用いる問題
ABC132-F Small Products 黄diffらしいです。
ARC150-B Make Divisible 良問ですね。
ABC296-D M<=ab 私は商列挙しました。
...少ないですね。
商列挙はそこまで使用頻度は高くないです。
2 おわりに
お読みいただきありがとうございました。
商列挙の証明が書きたくて書いたこの記事ですが書いていて結構勉強になりました。
よい競プロライフを！