C++で級数 K^n + K^(n-1)・(K-1) + … + (K-1)^n の合計を求める方法

この問題では、2つの整数 k と n が与えられます。級数 K^n + (K^(n-1) × (K-1)^1) + (K^(n-2) × (K-1)^2) + … + (K-1)^n の合計を求めるプログラムを作成するのが課題です。

問題を理解するための例

まず、具体的な入力と出力を見てみましょう。

入力: n = 3, k = 4
出力: 175
説明: 級数の合計は以下の通りです。
= 4^3 + ((4^2)×(3^1)) + ((4^1)×(3^2)) + ((4^0)×(3^3))
= 64 + 48 + 36 + 27 = 175

解法1：forループを使う単純なアプローチ

最もシンプルな方法は、forループを使って級数の各項を順番に計算し、その値を合計に加算していくことです。

アルゴリズム

sum = 0 で初期化
ステップ1: i を 0 から n まで繰り返す
ステップ1.1: sum += pow(k, n-i) * pow((k-1), i) で sum を更新
ステップ2: sum を返す

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
#include <math.h>
using namespace std;

int calcSeriesSum(int k, int n) {
    int sum = 0;
    for (int i = 0; i <= n; i++) {
        int p = pow(k, n-i) * pow((k-1), i);
        sum = sum + p;
    }
    return sum;
}

int main() {
    int n = 4;
    int K = 2;
    cout<<"級数の合計は "<<calcSeriesSum(K, n);
}

出力

級数の合計は 31

この解法は正しい結果を返しますが、各項を個別に計算して足し合わせるため、計算量は O(n) となり、n が大きくなると非効率です。

解法2：一般式を用いた効率的なアプローチ

より効率的な解法は、級数の合計を表す一般式（閉じた形式）を数学的に導出することです。

級数 K^n + (K^(n-1) × (K-1)^1) + (K^(n-2) × (K-1)^2) + … + (K-1)^n は等比数列です。
初項は k^n、公比は (k-1)/k となります。

sum = K^n + (K^(n-1) × (K-1)^1) + (K^(n-2) × (K-1)^2) + … + (K-1)^n
sum = k^n × (1 + (k-1)/k + (k-1)^2/k^2 + … + (k-1)^n)
sum = (k^n × (1 − ((k-1)^(n+1))/k^(n+1))) / (1 − ((k-1)/k))
sum = k^n × ((k^(n+1) − (k-1)^(n+1))/k^(n+1)) / ((k − (k-1))/k)
sum = k^n × ((k^(n+1) − (k-1)^(n+1))/k^(n+1)) / (1/k)
sum = k^n × ((k^(n+1) − (k-1)^(n+1))/k^(n+1)) × k
sum = k^(n+1) − (k-1)^(n+1)

このように、級数の合計は k^(n+1) − (k−1)^(n+1) という非常にシンプルな式で表せます。これにより、ループによる反復処理が不要になり、たった1回の計算で答えを求められるようになります。

実装例

公式を利用した解法のプログラムは以下の通りです。

#include <iostream>
#include <math.h>
using namespace std;

int calcSeriesSum(int k, int n) {
    return (pow(k, (n+1)) - pow((k-1), (n+1)));
}

int main() {
    int n = 4;
    int K = 2;
    cout<<"級数の合計は "<<calcSeriesSum(K, n);
}

出力

級数の合計は 31

まとめ

単純なループによる解法は O(n) の計算量が必要ですが、等比数列の和の公式から導出した k^(n+1) − (k−1)^(n+1) を使えば、反復処理なしに直接答えを計算でき、大幅に高速化できます。

注意： n や k が大きくなると、計算結果が int 型の範囲（約21億）を超える可能性があります。大きな入力を扱う場合は、戻り値や変数を long long 型に変更することをおすすめします。