AtCoder Beginner Contest 132 F / Small Products

AtCoder Beginner Contest 132 F / Small Products を解答ACしたので、
行間の証明をメモしておく。

問題はこれ
F - Small Products。

解説

以下、" $[$ "はガウス記号、" $\sharp A$ " は集合 $A$ の要素の個数とする。

自然数 $a, b$ の積が $N$ 以下になるようなものをどうやって求めればいいかを考える必要がある。

一つ Remark をしておく。

各 $a$ に対して、 $a \times b \leq N$ となる $b$ の数は、 $[\frac{N}{a}]$ である。

さて、

何か、 $[ \sqrt{N} ]$ を境目に別れるらしい。

これは、「 $a \leq [ \sqrt{N} ]$ かつ $b \geq [ \sqrt{N} ]$ 」または、

「 $a \geq [ \sqrt{N} ]$ かつ $b \leq [ \sqrt{N} ]$ 」が常に満たされるので、そんな気がする。

次のようなことを考えてみる。

$x$ を適当な自然数として、

いつ $[\frac{N}{x}] > [\frac{N}{x+1}]$ が満たされるかを調べてみる。

$\frac{N}{x} - 1 \geq \frac{N}{x+1}$ であればよい。

これを変形すると、

$N \geq x(x+1)$

となる。
つまり、

$\sqrt{N} \geq x$ であれば、 $[\frac{N}{x}] > [\frac{N}{x+1}]$ が満たされる。

従って、 $\sharp \{ [ \frac{N}{x}] \,| \,x \in \mathbb{N}, x \leq \sqrt{N}\} = [\sqrt{N}]$ であることが分かる。

さらに、正の実数 $x$ として、

$x > \sqrt{N} \Leftrightarrow \frac{N}{x} < \sqrt{N}$

という対称性から、

$\sharp \{ [ \frac{N}{x}] \,|\, x \in \mathbb{N}, x \geq \sqrt{N}\} = [\sqrt{N}]$

となることが分かる。

というわけで、この区間ごとに調べれば良い。

あとは、dp とか累積和とか使っていい感じにやればよい。

解答

Q = 10**9+7
from collections import deque
from itertools import accumulate
def main():
    N, K = map( int, input().split())
    ans = 0
    d = deque()
    e = deque()
    M = int(N**(1/2))*2
    for i in range(1, int(N**(1/2))+1):
        if i**2 == N:
            d.append(i)
            M -= 1
            continue
        d.append(i)
        e.appendleft(N//i)
    T = list(d)+list(e)
    CT = [1]*M
    for i in range(1,M):
        CT[i] = T[i] - T[i-1]
    accT = list( map(lambda x:x%Q, accumulate(CT) ))
    dp = [[0]*M for _ in range(K)]
    for i in range(M):
        dp[1][i] = accT[-i-1]*CT[i]%Q
    for k in range(1, K-1):
        accT[0] = dp[k][0]
        for i in range(M-1):
            accT[i+1] = (accT[i]+dp[k][i+1])%Q
        for i in range(M):
            dp[k+1][i] = accT[-i-1]*CT[i]%Q
    print(sum(dp[K-1])%Q)
    
if __name__ == '__main__':
    main()