Sum of Floor

無限にありそうな問題。

 1以上の整数とが与えられます。

を求めてね。

これを計算量くらいで解こう〜

解法(のとき)

1. baby-step?

を計算しよう。愚直にやればいいです。

2. GIANT=STEP?

とすると、です。

1以上の整数を決めたとき、なるの個数は二分探索で雑に求められるので、 回くらいのイテレーションでを全探索しながらに対するの個数を求めましょう。

こ〜ど

気をつけなければいけないことがあって、

• baby-stepとGIANT=STEPで数え上げのダブりがあってはならない

• になるようながない場合を警戒する

といった感じのことに気を配りながらコードを書きました。

N, M = map(int, input().split())

#naive
res = 0
for i in range(1, M + 1): res += N // i
print(res)


#cleverer
res = 0
sq = int(N ** 0.5)
for i in range(1, M + 1):
  if N // i <= sq: break
  res += N // i

for i in range(1, sq + 1):
  ok = M
  ng = 0
  while ok - ng > 1:
    m = (ok + ng) // 2
    if N // m <= i: ok = m
    else: ng = m
  l = ok

  ok = 0
  ng = M + 1
  while ng - ok > 1:
    m = (ok + ng) // 2
    if N // m >= i: ok = m
    else: ng = m
  r = ok
  if N // l == i: res += i * (r - l + 1)
print(res)

おしまい

あ〜あ この問題ratedのコンテストでうっかり出ねーかな
あと何となくlog落ちそうな感じがします