AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Regular Contest 091 D – Remainder Reminder
落ち着いて考えればやりかたは分かる問題だと思うが、きれいに実装するのがやや難し目の問題だと思う。
# AtCoder Regular Contest 091 D - Remainder Reminder
# https://atcoder.jp/contests/arc091/tasks/arc091_b
# tag: 整数 数え上げ 剰余 コーナーケース 高橋君
# a % b >= K (1 <= a <= N, 1 <= b <= N) が条件。
# a に対応する b を数えるのは大変そうなので、
# b を動かしながら、それぞれの a の個数を数えることにする。
# 以下、数えやすいように a を 0 ～ N の N+1 個の範囲で
# 動かすとする。
# b を固定して a を動かすと、a % bの値は
# (0, 1, 2, ..., b-1) の b 個の数をループすることになる。
# このループ中の、条件を満たす数は b - K 個。
# また、ループ自体は (N+1) // b 個がまるまる含まれる
# ことになるので、
# (b - K) * ((N+1) // b) 個の a が、まず存在する。
# ただし、K == 0 のケースのみ、0 が数えられてしまうので
# 1 引いておくこと。
# 加えて、(N + 1) % b 個のループの余りが存在する。
# ここに含まれる、条件を満たす数は
# max(0, (N + 1) % b - K) 個となる。
def main():
N, K = map(int, input().split())
result = 0
# b は明らかに K より大きい
for b in range(K+1, N+1):
# まるごと含まれるループ分を加算
num_in_loop = (b - K)
loop_n = (N + 1) // b
result += num_in_loop * loop_n
# 便宜上 a を 0 からとして考えているので、
# 含まれてしまう場合は 1 引いておく。
if K == 0:
result -= 1
# ループの余り分を加算
remainder = (N + 1) % b
result += max(0, remainder - K)
print(result)
main()
関連
