C++でn番目の項がn²−(n−1)²となる級数の和を求める方法

この問題では、整数値Nが与えられます。私たちのタスクは、n番目の項が n² − (n−1)² となる級数の、第n項までの和を求めることです。

問題の例

入力：N = 3
出力：9

説明：

[12 − 02] + [22 − 12] + [32 − 22] = 1 + 3 + 5 = 9

解法のアプローチ

この問題を効率的に解くには、級数の一般項を求め、そこから第n項までの和を表す公式を導出します。公式を使って直接計算できれば、計算時間をO(1)に抑えることができます。また、結果が非常に大きな値になる可能性があるため、剰余（mod）を取る必要があります。

まず、級数の第n項の公式を導出してみましょう。

$T_{n} = \mathrm{n^2-(n-1)^2}$

a² − b² = (a+b)(a−b) の公式を使って展開すると、

$T_{n} = \mathrm{(n+(n-1)) \times (n-(n-1))}$

$= \mathrm{(2n-1) \times 1}$

$= \mathrm{2n-1}$

この一般項を使えば、第n項までの和は次のように求められます。

$\mathrm{sum} = \sum(2n-1)$

$\mathrm{sum} = 2\sum{n} - \sum{1}$

$\mathrm{sum} = 2 \times \frac{n(n+1)}{2} - n$

$\mathrm{sum} = n(n+1) - n = n^2 + n - n = n^2$

つまり、この級数の和は n² となります。n² は非常に大きな数になりうるため、計算結果に対して剰余を取ります。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include<iostream>
using namespace std;
#define mod 1000000007
long long calcSumNTerms(long long n) {
    return ((n%mod)*(n%mod))%mod;
}
int main() {
    long long n = 4325353;
    cout<<"第n項までの級数の和は "<<calcSumNTerms(n);
    return 0;
}

出力

第n項までの級数の和は 678443653

コードの解説

calcSumNTerms関数では、まずnをmodで割った余りを求め、その値同士を掛け合わせた後、再度modを取ることで、オーバーフローを防ぎながら n² mod 1000000007 を計算しています。このように各段階で剰余を取ることで、大きなnに対しても安全に計算できます。

計算量の分析

時間計算量：O(1) — 公式を用いて直接計算するため、nの大きさに関わらず定数時間で完了します。

空間計算量：O(1) — 追加のメモリは一切必要ありません。