[AtCoder] ABC 190 D – Staircase Sequences
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません