問題：AtCoder Beginner Contest 190: D - Staircase Sequences

解説

解説PDFまんまです。

初項a, 末項b とすると、数列は[a, a+1, ... , b-1, b]と表現できる

この数列の総和をSとすると、

$S = \frac{(a+b)(b-a+1)}{2}$

今回の問題では $S = N$ より、

$N = \frac{(a+b)(b-a+1)}{2}$ 　　 $(a \leq b)$

両辺2倍すると、

$2N = (a+b)(b-a+1) 　　(a \leq b)・・・★$

となる。これを満たす $(a, b)$ の組の個数を求める問題である。

このとき、

$A=a+b$

$B=b-a+1$

とおくと★は、

$2N = AB$

となる。

$A, B$ はそれぞれ正整数なので、 $(A, B)$ の組はそれぞれ $2N$ の約数といえる。

なので $2N$ の約数を列挙して（ $O(\sqrt(2N))でできる$ ）、 $2N$ の約数 $A, B$ について、

$A = a + b・・・①$

$B = b-a+1・・・②$

が成立する個数を数えたい。

①より $a = A - b$ より、これを②に代入すると、

$B = b-(A-b)+1$

式変形すると、

$B+A-1 = 2b$

この式を満たすものを数えればよい。

つまり、 $B+A-1が偶数$ の個数を数えれば良い。

例として、入力例1のN = 12のときを考える。

数列はそれぞれ

[12]
[3,4,5]
[-2, -1, ... ,4, 5]
[-11, -10, ..., 11, 12]

になるらしいが、それぞれ①と②にaとbを代入してみると、

a=12, b=12 ⇒ A=24, B=1
a=3, b=5 ⇒ A=8, B=3
a=-2, b=5 ⇒ A=3, B=8
a=-11, b=12 ⇒ A=1, B=24

となる。

A, Bはそれぞれ2N=24の約数になっていることがわかる。

コーナーケース

特になし

実装

# -*- coding:utf-8 -*-

def diviser(n):
    """約数を列挙して返す"""
    ans = []
    i = 1
    while True:
        if i*i > n: break
        m = n%i
        if m==0:
            ans.append(i)
            if not n//i in ans:
                ans.append(n//i)
        i += 1
    return ans


def solve():
    N = int(input())
    ans = 0

    divs = diviser(2*N)
    divs.sort()

    for i in range(len(divs)):
        A, B = divs[-i-1], divs[i]
        if B>A: break

        """
        A = a+b
        B = b-a+1
        をそれぞれ満たすか？
        すなわち式変形して、
        B+A-1 = 2bを満たすか？
        つまりB+A-1は偶数か？
        """
        if (B+A-1)&1==0:
            ans += 2

    print(ans)


if __name__ == "__main__":
    solve()