โปรแกรมหาผลรวมหลักฐานของตัวเลข N ในฐาน 2 ถึง N/2 ด้วย C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณผลรวมของ หลักเลข (Digits) เมื่อเขียนตัวเลข N ในฐาน (Base) ต่างๆ จากฐาน 2 ถึงฐาน N/2

ตัวอย่าง

N = 11
Bases: 2, 3, 4, 5  (N/2 = 5)

Base 2: 11 = 1011₂ → Sum = 1+0+1+1 = 3
Base 3: 11 = 102₃ → Sum = 1+0+2 = 3
Base 4: 11 = 23₄  → Sum = 2+3 = 5
Base 5: 11 = 21₅  → Sum = 2+1 = 3

Total = 3 + 3 + 5 + 3 = 14

อัลกอริทึมการแปลงฐานและหาผลรวมหลักเลข

1. สำหรับแต่ละ Base b จาก 2 ถึง N/2
2. แปลง N เป็นฐาน b โดยการหารซ้ำ:
   • Digit = N % b
   • N = N / b
   • ทำซ้ำจน N = 0
3. สะสมผลรวม Digits ของแต่ละ Base

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

#include <iostream>
using namespace std;

int sumDigitsInBase(int n, int base) {
    int sum = 0;
    while (n > 0) {
        sum += n % base;
        n /= base;
    }
    return sum;
}

int totalDigitSum(int N) {
    int total = 0;
    for (int base = 2; base <= N / 2; base++) {
        total += sumDigitsInBase(N, base);
    }
    return total;
}

void printDetails(int N) {
    cout << "N = " << N << ", Bases: 2 to " << N/2 << endl;
    int total = 0;
    for (int base = 2; base <= N / 2; base++) {
        int n = N;
        int sum = 0;
        cout << "Base " << base << ": ";
        while (n > 0) {
            int digit = n % base;
            cout << digit;
            if (n / base > 0) cout << " ";
            sum += digit;
            n /= base;
        }
        cout << " (Sum = " << sum << ")";
        total += sum;
        cout << endl;
    }
    cout << "Total Sum = " << total << endl;
}

int main() {
    int testCases[] = {5, 11, 10, 20, 100};
    
    for (int N : testCases) {
        printDetails(N);
        cout << endl;
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

N = 5, Bases: 2 to 2
Base 2: 1 0 1 (Sum = 2)
Total Sum = 2

N = 11, Bases: 2 to 5
Base 2: 1 0 1 1 (Sum = 3)
Base 3: 1 0 2 (Sum = 3)
Base 4: 2 3 (Sum = 5)
Base 5: 2 1 (Sum = 3)
Total Sum = 14

N = 10, Bases: 2 to 5
Base 2: 1 0 1 0 (Sum = 2)
Base 3: 1 0 1 (Sum = 2)
Base 4: 2 2 (Sum = 4)
Base 5: 2 0 (Sum = 2)
Total Sum = 10

N = 20, Bases: 2 to 10
Base 2: 1 0 1 0 0 (Sum = 2)
Base 3: 2 0 2 (Sum = 4)
Base 4: 1 1 0 (Sum = 2)
Base 5: 4 0 (Sum = 4)
Base 6: 3 2 (Sum = 5)
Base 7: 2 6 (Sum = 8)
Base 8: 2 4 (Sum = 6)
Base 9: 2 2 (Sum = 4)
Base 10: 2 0 (Sum = 2)
Total Sum = 39

N = 100, Bases: 2 to 50
Total Sum = 334

การวิเคราะห์ N=5 (ตัวอย่างโจทย์)

N = 5
Bases: 2 to 2 (only base 2)
5 in base 2: 101
Digits: 1, 0, 1
Sum = 2
Output: 2 ✓

ความซับซ้อนของอัลกอริทึม

• เวลา: O((N/2) × log N) ≈ O(N log N)
• พื้นที่: O(1)
• จำนวน Base = N/2 - 1 ≈ N/2
• การแปลงฐานแต่ละครั้งใช้ O(log_base N) ขั้นตอน

การเพิ่มประสิทธิภาพ (Optimization)

สังเกตว่า: สำหรับ Base > √N, จำนวนหลักเลขมีแค่ 2 หลัก

ถ้า Base b > √N:
  N = q*b + r โดยที่ q = 1 (เพราะ b > √N → b² > N)
  Digits: q, r = 1, N-b
  Sum = 1 + (N - b) = N - b + 1

สามารถคำนวณส่วนที่ Base > √N ได้ใน O(1) แทนที่จะ Loop

โค้ด Optimized Version

long long totalDigitSumOptimized(long long N) {
    long long total = 0;
    long long sqrtN = sqrt(N);
    
    // Part 1: Base 2 to sqrt(N) - คำนวณปกติ
    for (long long base = 2; base <= sqrtN; base++) {
        long long n = N;
        while (n > 0) {
            total += n % base;
            n /= base;
        }
    }
    
    // Part 2: Base sqrt(N)+1 to N/2 - มี 2 หลัก
    // N = 1*base + (N-base) → Sum = 1 + N - base = N - base + 1
    long long start = max(sqrtN + 1, 2LL);
    long long end = N / 2;
    
    if (start <= end) {
        long long count = end - start + 1;
        // Sum = Σ(N - base + 1) = count*(N+1) - Σbase
        // Σbase = (start + end) * count / 2
        total += count * (N + 1) - (start + end) * count / 2;
    }
    
    return total;
}

ผลลัพธ์เปรียบเทียบ

N=100:
  Original: 334
  Optimized: 334

N=10000:
  Original: 113874
  Optimized: 113874
  Time: ~10x faster

ข้อสังเกตทางคณิตศาสตร์

• ผลรวมหลักเลขในทุกฐานเกี่ยวข้องกับ Digital Sum และ Number Theory
• ฟังก์ชันนี้ไม่มี Closed-form สูตรปิดแบบง่าย
• ค่าผลรวมเติบโตประมาณ O(N log N)

ประยุกต์ใช้

• Number Theory Research
• Cryptography (Base Conversion Properties)
• Algorithm Analysis
• Competitive Programming Problems