😸

ABC190 D - Staircase Sequences

1 min read

問題概要

公差1の等差数列で和がNになるものはいくつあるか

解法

公差がわかっているので初項と長さを決めてやれば数列が定まる
初項S, 長さLとすると

A = \{S, S+1, ..., S+L-1\}
和は\frac{L* (S + S+L-1)}{2} = \frac{L* (2S+L-1)}{2}となり

N = \frac{L* (2S+L-1)}{2}となる

式変形すると

2N = L * (2S+L-1)

Lおよび2S+L-1は2Nの約数になっている
そして(2S+L-1) - L = 2S-1であり、約数の片方から片方を引いたものは奇数になっている
2Nの約数を列挙して、条件を満たすものがあれば、答えに+1すればいい

提出コード

https://atcoder.jp/contests/abc190/submissions/19823950

コンテスト中に解けなかったのがだいぶ悔しい

Discussion

ログインするとコメントできます