Sum of Series K^n + K^(n-1)(K-1) + ... + (K-1)^n ใน C++

โจทย์: หาผลรวมอนุกรม: K^n + K^(n-1)(K-1)^1 + K^(n-2)(K-1)^2 + ... + (K-1)^n

ตัวอย่าง: n=3, K=4 → 4³ + 4²·3 + 4·3² + 3³ = 64+48+36+27 = 175

วิธี 1: Loop ทีละพจน์ (O(n))

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

วิธี 2: สูตร Closed-form (O(1))

อนุกรมเป็น Geometric Progression:

• First term: a = K^n
• Common ratio: r = (K-1)/K
• Number of terms: n+1

Sum = a (1 - r^(n+1)) / (1 - r) = K^n (1 - ((K-1)/K)^(n+1)) / (1/K) = K^(n+1) - (K-1)^(n+1)

ตัวอย่างโค้ด C++ (Optimized)

#include <iostream>
#include <cmath>
using namespace std;

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

int main() {
    int n = 4, K = 2;
    cout << "Sum: " << calcSeriesSum(K, n); // 31
}

อินพุต

n=4, K=2

เอาต์พุท

Sum: 31

Verification

K=2, n=4: 2⁵ - 1⁵ = 32 - 1 = 31 ✓
Series: 16 + 8 + 4 + 2 + 1 = 31 ✓

Complexity

• Loop: O(n) time, O(1) space
• Formula: O(log n) time (pow), O(1) space