[AtCoder] ABC 163 D – Sum of Large Numbers

2020年4月25日

問題

方針

\( n \) 個の自然数から任意の個数の和の組み合わせは、

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

となります。これは、最大値が \( n \) 個の和であるためです。ここで、関数 \( f(x) \) を

\[f(x) = \dfrac{x(x + 1)}{2}\]

とします。\( n \) 個の自然数から \( k \) 個の最大値は、\(f(n) – f(n – k)\) となり、最小値は、\( f(k) \) となるので、組み合わせは、

\[f(n) – f(n – k) – f(k) + 1\]

となります。これを \( k = K \) から \( k = N + 1 \) まで足し合わせれば良いです。

コード