[AtCoder] ABC 190 D – Staircase Sequences

2021年2月17日2021年2月18日

問題

方針

\( 0 \) 以上の連続する \( n \) 個の整数の和は

\[ \dfrac{n(n + 1)}{2}\]

となります。したがって、連続する自然数の和は、整数 \( n , m \ (0 \leq m < n) \) を用いて、

\[ \dfrac{n(n + 1)}{2} – \dfrac{m(m + 1)}{2}\]

となります。これが、\( 2N \) となるような \( n, m \) の組を求めます。

\[\begin{eqnarray}
\dfrac{n(n + 1)}{2} – \dfrac{m(m + 1)}{2} &=& N\\
(n + m – 1)(n – m) &=& 2N
\end{eqnarray}\]

ここで、\( pq = 2N \ ( q < p) \) を満たす自然数 \( p, q \) を求められたとすると、次の連立方程式が得られます。

\begin{cases}
n + m + 1 &=& p \\
n – m &=& q
\end{cases}

したがって、

\[ (n, m) = \left ( \dfrac{p + q – 1}{2}, \dfrac{p – q + 1}{2} \right )\]

が得られます。ここで、\( q \) の範囲は、\( 1 \leq q < \sqrt{N} \) なので全探索を行います。これらの方針では、負の値を考えていないので、求められた \( (n, m) \) の組み合わせの数の \( 2 \) 倍が答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll N;
    cin >> N;
    int ans = 0;
    for (ll i = 1; i * i < 2 * N; i++) {
        if ((2 * N) % i == 0) {
            ll p = (2 * N) / i;
            ll q = i;
            if ((p + q - 1) % 2 == 0 && (p - q - 1) % 2 == 0) ans ++;
        }
    }
    cout << 2 * ans << "\n";
    return 0;
}